QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#186325#6396. Puzzle: Kusabiucup-team228#WA 29ms12636kbC++203.8kb2023-09-23 17:03:052023-09-23 17:03:06

Judging History

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

  • [2023-09-23 17:03:06]
  • 评测
  • 测评结果:WA
  • 用时:29ms
  • 内存:12636kb
  • [2023-09-23 17:03:05]
  • 提交

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()) {
            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].first]) {
                        return false;
                    } else {
                        dead[cur[i].first] = true;
                        nxt.emplace_back(par[cur[i].first], 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
}

詳細信息

Test #1:

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

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: 9632kb

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: 9384kb

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 29ms
memory: 12636kb

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:

YES
28763 79617
61327 78961
41090 52589
7241 8873
8241 69010
19874 85932
33789 58699
3681 15911
24772 27446
79799 95031
28194 83333
3283 78400
3156 31315
14132 59851
93895 69894
5411 71680
2042 19510
60418 62556
34214 79826
2267 7602
2564 13533
22026 80131
54276 63173
13236 75831
10051 10691
8051 18...

result:

wrong answer Pair 46131-42353 symbol not satisfied.