QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#186323#6396. Puzzle: Kusabiucup-team228#WA 22ms11984kbC++204.0kb2023-09-23 16:59:232023-09-23 16:59:23

Judging History

你现在查看的是最新测评结果

  • [2023-09-23 16:59:23]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:11984kb
  • [2023-09-23 16:59:23]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
int par[N], type[N];
vector<int> g[N];
int timer = 0;
int t_in[N], t_out[N];
int depth[N];

vector<int> level[N];
bool dead[N];

vector<pair<int, int>> ans;
int carry[N];

void dfs1(int v) {
    t_in[v] = ++timer;
    if (type[v] == 3) {
        level[depth[v]].push_back(v);
    }
    for (int to : g[v]) {
        depth[to] = depth[v] + 1;
        dfs1(to);
    }
    t_out[v] = ++timer;
}

bool dfs2(int v) {
    vector<pair<int, int>> up;
    set<pair<int, int>> down;
    for (int to : g[v]) {
        if (!dead[to]) {
            if (!dfs2(to)) {
                return false;
            }
            if (carry[to]) {
                if (type[carry[to]] == 1) {
                    down.emplace(depth[carry[to]], carry[to]);
                } else if (type[carry[to]] == 2) {
                    up.emplace_back(depth[carry[to]], carry[to]);
                } else {
                    assert(false);
                }
            }
        }
    }
    if (type[v] == 1) {
        down.emplace(depth[v], v);
    } else if (type[v] == 2) {
        up.emplace_back(depth[v], v);
    }
    sort(up.begin(), up.end());
    vector<int> extra_up, extra_down;
    while (!up.empty()) {
        auto [dep, u] = up.back();
        up.pop_back();
        auto it = down.upper_bound({dep, 0});
        if (it == down.end()) {
            extra_up.push_back(u);
        } else {
            ans.emplace_back(u, it->second);
            down.erase(it);
        }
    }
    for (auto [dep, u] : down) {
        extra_down.push_back(u);
    }
    if (extra_down.size() + extra_up.size() >= 2) {
        return false;
    } else if (!extra_down.empty()) {
        carry[v] = extra_down[0];
    } else if (!extra_up.empty()) {
        carry[v] = extra_up[0];
    }
    return true;
}

bool solve(int n) {
    dfs1(1);
    dead[1] = true;
    for (int d = 0; d <= n; d++) {
        if (level[d].size() & 1) {
            return false;
        }
        vector<pair<int, int>> cur;
        for (int v : level[d]) {
            cur.emplace_back(v, v);
        }
        while (!cur.empty()) {
//            for (auto [p, v] : cur) {
//                cout << "(" << p << ", " << v << ") ";
//            }
//            cout << "\n";
            vector<pair<int, int>> nxt;
            for (int i = 0; i < cur.size(); i++) {
                if (i + 1 < cur.size() && cur[i].first == cur[i + 1].first) {
                    ans.emplace_back(cur[i].second, cur[i + 1].second);
                    i++;
                } else {
                    if (dead[cur[i].second]) {
                        return false;
                    } else {
                        dead[cur[i].second] = true;
                        nxt.emplace_back(par[cur[i].second], cur[i].second);
                    }
                }
            }
            swap(cur, nxt);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (dead[i]) {
            if (!dfs2(i)) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int waste;
        string t;
        cin >> waste >> par[i] >> t;
        if (t == "-") {
            type[i] = 0;
        } else if (t == "Chang") {
            type[i] = 1;
        } else if (t == "Duan") {
            type[i] = 2;
        } else {
            type[i] = 3;
        }
        g[par[i]].push_back(i);
    }

    if (solve(n)) {
        cout << "YES\n";
        for (auto [u, v] : ans) {
            cout << u << " " << v << "\n";
        }
    } else {
        cout << "NO\n";
    }

#ifdef LOCAL
    cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9472kb

input:

8
2 1 -
3 1 -
4 2 Tong
5 2 Tong
6 3 Duan
7 3 -
8 7 Chang

output:

YES
4 5
6 8

result:

ok Correct.

Test #2:

score: 0
Accepted
time: 0ms
memory: 9408kb

input:

10
2 1 Duan
3 2 Duan
4 2 -
5 4 Chang
6 2 Chang
7 1 Duan
8 6 Tong
9 6 Tong
10 3 Chang

output:

YES
8 9
3 10
2 6
7 5

result:

ok Correct.

Test #3:

score: 0
Accepted
time: 0ms
memory: 9764kb

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 22ms
memory: 11984kb

input:

100000
2 1 Duan
3 1 Duan
4 3 -
5 4 Duan
6 3 -
7 4 Duan
8 4 -
9 8 -
10 7 Duan
11 9 -
12 7 Duan
13 7 Duan
14 8 Duan
15 13 -
16 10 Duan
17 11 Duan
18 12 -
19 1 Duan
20 5 Duan
21 4 Duan
22 14 Duan
23 16 -
24 22 Duan
25 16 Duan
26 13 -
27 13 -
28 17 -
29 5 Duan
30 22 -
31 23 -
32 9 Duan
33 5 -
34 30 Duan...

output:

NO

result:

wrong answer Jury has answer but participant has not.