QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104901#6396. Puzzle: Kusabickiseki#WA 34ms8308kbC++203.8kb2023-05-12 13:35:372023-05-12 13:35:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-12 13:35:39]
  • 评测
  • 测评结果:WA
  • 用时:34ms
  • 内存:8308kb
  • [2023-05-12 13:35:37]
  • 提交

answer

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

#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

void fail() {
    cout << "NO\n";
    exit(0);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> dep(n);
    vector<int> p(n);

    vector<char> type(n);
    vector<vector<int>> g(n);

    for (int i = 1; i < n; i++) {
        int z;
        string t;
        cin >> z >> p[i] >> t;
        --p[i];
        dep[i] = dep[p[i]] + 1;
        g[p[i]].push_back(i);
        if (t == "Tong") {
            type[i] = 'T';
        } else if (t == "Chang") {
            type[i] = 'L';
        } else if (t == "Duan") {
            type[i] = 'S';
        } else {
            type[i] = '-';
        }
    }

    vector<pair<int,int>> ans;

    const auto dfs = [&](auto self, int i) -> tuple<char,int,int> {
        map<int,int> T;
        vector<pair<int,int>> L, S;

        const auto upd = [&T, &L, &S, &ans](char tt, int dd, int id) {
            if (tt == 'T') {
                if (auto it = T.find(dd); it != T.end()) {
                    ans.emplace_back(it->second, id);
                    T.erase(it);
                } else {
                    T[dd] = id;
                }
                return;
            }

            if (tt == 'L') {
                L.emplace_back(dd, id);
            } else if (tt == 'S') {
                S.emplace_back(dd, id);
            }


        };

        upd(type[i], dep[i], i);
        for (int j: g[i]) {
            auto [tz, dz, z] = self(self, j);
            upd(tz, dz, z);
        }

        if (abs(int(L.size()) - int(S.size())) + T.size() > 1) {
            fail();
        }

        assert (T.size() <= 1 ||
                L.size() == S.size() || L.size() == S.size() + 1
                || L.size() + 1 == S.size());

        sort(L.begin(), L.end());
        sort(S.begin(), S.end());
        if (T.size() == 1 || L.size() == S.size()) {
            for (size_t pos = 0; pos < L.size(); pos++) {
                if (L[pos].first <= S[pos].first)
                    fail();
                ans.emplace_back(L[pos].second, S[pos].second);
            }

            if (T.size() == 0)
                return { '-', -1, -1 };
            auto [dd, ii] = *T.begin();
            return { 'T', dd, ii };
        }

        if (L.size() == S.size() + 1) {
            for (size_t pos = 0; pos + 1 < L.size(); pos++) {
                if (L[pos].first <= S[pos].first)
                    fail();
                ans.emplace_back(L[pos].second, S[pos].second);
            }

            auto [dd, ii] = L.back();
            return { 'L', dd, ii };
        }

        if (L.size() + 1 == S.size()) {
            for (size_t pos = 1; pos < S.size(); pos++) {
                if (L[pos - 1].first <= S[pos].first)
                    fail();
                ans.emplace_back(L[pos - 1].second, S[pos].second);
            }

            auto [dd, ii] = S.front();
            return { 'S', dd, ii };
        }

        __builtin_unreachable();
    };

    auto [tz, dz, z] = dfs(dfs, 0);
    if (tz != '-') {
        fail();
    }

    cout << "YES\n";
    for (auto [x, y]: ans) {
        cout << x + 1 << ' ' << y + 1 << '\n';
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

YES
4 5
8 6

result:

ok Correct.

Test #2:

score: 0
Accepted
time: 2ms
memory: 3456kb

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

result:

ok Correct.

Test #3:

score: 0
Accepted
time: 2ms
memory: 3412kb

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 34ms
memory: 8308kb

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.