QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#243684#6396. Puzzle: Kusabiucup-team1198#WA 2ms6116kbC++205.7kb2023-11-08 15:50:062023-11-08 15:50:07

Judging History

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

  • [2023-11-08 15:50:07]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:6116kb
  • [2023-11-08 15:50:06]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

const int MAXN = 1e5 + 100;
vector<int> g[MAXN];
int deapth[MAXN];
char tp[MAXN];

pair<char, int> dp[MAXN];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    tp[0] = '-';
    deapth[0] = 0;
    for (int i = 1; i < n; ++i) {
        int useless, p;
        string s;
        cin >> useless >> p >> s;
        --p;
        g[p].push_back(i);
        deapth[i] = deapth[p] + 1;
        if (s[0] == 'T') {
            tp[i] = 't';
        } else if (s[0] == 'D') {
            tp[i] = 'd';
        } else if (s[0] == 'C') {
            tp[i] = 'c';
        } else {
            tp[i] = '-';
        }
    }

    vector<array<int, 2>> ans;

    for (int v = n - 1; v >= 0; --v) {
        /// cerr << v << endl;
        vector<int> c, d;
        vector<int> t;
        for (int u : g[v]) {
            if (dp[u].first == 't') {
                t.push_back(dp[u].second);
            } else if (dp[u].first == 'c') {
                c.push_back(dp[u].second);
            } else if (dp[u].first == 'd') {
                d.push_back(dp[u].second);
            }
        }
        if (tp[v] == 't') {
            t.push_back(v);
        } else if (tp[v] == 'c') {
            c.push_back(v);
        } else if (tp[v] == 'd') {
            d.push_back(v);
        }
        auto cmp = [](int u, int v) {
            return deapth[u] < deapth[v];
        };
        sort(c.begin(), c.end(), cmp);
        sort(d.begin(), d.end(), cmp);
        sort(t.begin(), t.end(), cmp);
        dp[v] = {'-', -1};
        if (c.size() > d.size()) {
            dp[v].first = 'c';
            if (c.size() > d.size() + 1) {
                cout << "NO\n";
                return 0;
            }
            if (t.size() % 2 == 1) {
                cout << "NO\n";
                return 0;
            }
            int cur = 0;
            for (int i = 0; i < (int)d.size(); ++i) {
                if (deapth[d[i]] < deapth[c[cur]]) {
                    ans.push_back({d[i], c[cur]});
                    ++cur;
                    continue;
                } else {
                    if (dp[v].second != -1) {
                        cout << "NO\n";
                        return 0;
                    }
                    dp[v].second = c[cur];
                    ++cur;
                    --i;
                    continue;
                }
            }
            if (dp[v].second == -1) {
                dp[v].second = c.back();
            }
            for (int i = 0; i < (int)t.size(); i += 2) {
                if (deapth[t[i]] != deapth[t[i + 1]]) {
                    cout << "NO\n";
                    return 0;
                }
                ans.push_back({t[i], t[i + 1]});
            }
        } else if (c.size() < d.size()) {
            dp[v].first = 'd';
            if (d.size() > c.size() + 1) {
                cout << "NO\n";
                return 0;
            }
            if (t.size() % 2 == 1) {
                cout << "NO\n";
                return 0;
            }
            int cur = (int)d.size() - 1;
            for (int i = (int)c.size() - 1; i >= 0; --i) {
                if (deapth[c[i]] > deapth[d[cur]]) {
                    ans.push_back({c[i], d[cur]});
                    --cur;
                    continue;
                } else {
                    if (dp[v].second != -1) {
                        cout << "NO\n";
                        return 0;
                    }
                    dp[v].second = d[cur];
                    --cur;
                    ++i;
                    continue;
                }
            }
            if (dp[v].second == -1) {
                dp[v].second = d[0];
            }
            for (int i = 0; i < (int)t.size(); i += 2) {
                if (deapth[t[i]] != deapth[t[i + 1]]) {
                    cout << "NO\n";
                    return 0;
                }
                ans.push_back({t[i], t[i + 1]});
            }
        } else if (t.size() % 2 == 1) {
            dp[v].first = 't';
            for (int i = 0; i < (int)c.size(); ++i) {
                if (deapth[c[i]] > deapth[d[i]]) {
                    ans.push_back({c[i], d[i]});
                } else {
                    cout << "NO\n";
                    return 0;
                }
            }
            for (int i = 0; i < (int)t.size() - 1; i += 2) {
                if (deapth[t[i]] == deapth[t[i + 1]]) {
                    ans.push_back({t[i], t[i + 1]});
                } else {
                    if (dp[v].second != -1) {
                        cout << "NO\n";
                        return 0;
                    }
                    dp[v].second = t[i];
                    --i;
                }
            }
            if (dp[v].second == -1) {
                dp[v].second = t.back();
            }
        } else {
            dp[v] = {'-', -1};
            /// cerr << "v: " << v << endl;
            for (int i = 0; i < (int)c.size(); ++i) {
                if (deapth[c[i]] > deapth[d[i]]) {
                    ans.push_back({c[i], d[i]});
                } else {
                    cout << "NO\n";
                    return 0;
                }
            }
            /// cerr << "v: " << v << endl;
            for (int i = 0; i < (int)t.size(); i += 2) {
                if (deapth[t[i]] == deapth[t[i + 1]]) {
                    ans.push_back({t[i], t[i + 1]});
                } else {
                    cout << "NO\n";
                    return 0;
                }
            }
        }
    }
    cout << "YES\n";
    for (auto elem : ans) {
        cout << elem[0] + 1 << " " << elem[1] + 1 << "\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

YES
8 6
4 5

result:

ok Correct.

Test #2:

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

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

result:

ok Correct.

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 6116kb

input:

2
2 1 Tong

output:

YES

result:

wrong answer Only odd number of marked vertices to match.