QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#629569 | #6396. Puzzle: Kusabi | Martian148 | WA | 51ms | 8032kb | C++20 | 2.9kb | 2024-10-11 13:20:08 | 2024-10-11 13:20:09 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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.