QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#629569#6396. Puzzle: KusabiMartian148WA 51ms8032kbC++202.9kb2024-10-11 13:20:082024-10-11 13:20:09

Judging History

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

  • [2024-10-11 13:20:09]
  • 评测
  • 测评结果:WA
  • 用时:51ms
  • 内存:8032kb
  • [2024-10-11 13:20:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

void NO() {
    cout << "NO" << endl;
    exit(0);
}

int main() {
    int n; cin >> n;
    vector<vector<int>> g(n + 1);
    vector<char> op(n + 1);
    vector<int> dep(n + 1, 0);
    for (int i = 2; i <= n; i++) {
        int x, fa; cin >> x >> fa;
        g[fa].push_back(x); dep[x] = dep[fa] + 1;
        string s; cin >> s;
        op[x] = s[0];
    }

    vector<pair<int,int>> ans;

    function<bool(int, int)> cmp = [&] (int x, int y) {
        return dep[x] < dep[y];
    };

    function<int(int)> dfs = [&] (int u) {
        vector<int> T, D, C;
        for (int v : g[u]) {
            int t = dfs(v);
            if (t == 0) continue;
            if (op[t] == 'T') T.push_back(t);
            if (op[t] == 'D') D.push_back(t);
            if (op[t] == 'C') C.push_back(t);
        }
        if (op[u] == 'T') T.push_back(u);
        if (op[u] == 'D') D.push_back(u);
        if (op[u] == 'C') C.push_back(u);

        int ret = 0;
        sort(T.begin(), T.end(), cmp);
        int i, j;
        for (i = 0; i + 1 < T.size();) {
            if (dep[i] == dep[i + 1]) {
                ans.push_back({T[i], T[i + 1]});
                i += 2;
            }
            else {
                if (ret == 0) {ret = T[i]; i += 1;}
                else NO();
            }
        }
        if (i < T.size()) {
            if (ret == 0) {ret = T[i]; i += 1;}
            else NO();
        }
        sort(D.begin(), D.end(), cmp);
        sort(C.begin(), C.end(), cmp);
        if (D.size() == C.size()) {
            for (i = 0; i < D.size(); i++) 
                if (dep[D[i]] < dep[C[i]])
                    ans.push_back({D[i], C[i]});
                else NO();
        }
        else if (D.size() == C.size() + 1) {
            for (i = 0, j = 0; i < C.size(); i++) {
                if (dep[D[j]] < dep[C[i]]) {
                    ans.push_back({D[j], C[i]});
                    j += 1; 
                }
                else if (ret == 0) {ret = D[j]; j += 1;}
                else NO();
            }
            if (j < D.size()) {
                if (ret == 0) {ret = D[j];}
                else NO();
            }
        }
        else if (D.size() + 1 == C.size()) {
            for (i = 0, j = 0; i < D.size(); i++) {
                if (dep[D[i]] < dep[C[j]]) {
                    ans.push_back({D[i], C[j]});
                    j += 1;
                }
                else if (ret == 0) {ret = C[j]; j += 1;}
                else NO();
            }
            if (j < C.size()) {
                if (ret == 0) {ret = C[j]; }
                else NO();
            }
        }
        else NO();

        return ret;
    };

    int root = dfs(1);
    if (root != 0) NO();
    cout << "YES" << '\n';
    for (auto p : ans) cout << p.first << " " << p.second << '\n';
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

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

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
3 10
8 9
2 6
7 5

result:

ok Correct.

Test #3:

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

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 51ms
memory: 8032kb

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.