QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104893#6396. Puzzle: Kusabickiseki#WA 30ms4996kbC++142.0kb2023-05-12 12:25:072023-05-12 12:25:09

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 12:25:09]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:4996kb
  • [2023-05-12 12:25:07]
  • 提交

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

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

    vector<pair<int,int>> ans;

    map<int,int> tong;

    vector<pair<int,int>> L, S;

    for (int i = 1; i < n; i++) {
        int z;
        string t;
        cin >> z >> p[i] >> t;
        --p[i];
        dep[i] = dep[p[i]] + 1;
        if (t == "Tong") {
            if (auto it = tong.find(dep[i]); it != tong.end()) {
                ans.emplace_back(it->second, i);
                tong.erase(it);
            } else {
                tong[dep[i]] = i;
            }
        } else if (t == "Chang") {
            L.emplace_back(dep[i], i);
        } else if (t == "Duan") {
            S.emplace_back(dep[i], i);
        }
    }

    sort(L.begin(), L.end());
    sort(S.begin(), S.end());

    if (L.size() != S.size()) {
        cout << "NO\n";
        return 0;
    }
    if (!tong.empty()) {
        cout << "NO\n";
        return 0;
    }

    for (size_t i = 0; i < L.size(); i++) {
        if (L[i].first <= S[i].first) {
            cout << "NO\n";
            return 0;
        }
        ans.emplace_back(L[i].second, S[i].second);
    }

    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: 0ms
memory: 3440kb

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

result:

ok Correct.

Test #3:

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

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 30ms
memory: 4996kb

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
59 130
109 227
237 305
331 355
366 423
376 431
546 553
200 597
326 631
610 674
432 859
827 863
794 868
885 945
621 984
867 1005
914 1048
1035 1079
1015 1104
893 1164
985 1199
1174 1262
541 1270
944 1289
1205 1348
1300 1356
1404 1427
1246 1479
1513 1557
1304 1598
1430 1611
1449 1631
1450 1665
126...

result:

wrong answer Edge 8-4 used twice.