QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104771 | #6396. Puzzle: Kusabi | gapinho# | WA | 3ms | 6372kb | C++20 | 3.3kb | 2023-05-11 22:13:20 | 2023-05-11 22:13:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = __int128_t;
#define int long long
using ii = pair<int, int>;
#define endl '\n'
const int ms = 1e5+50;
const int mod = 998244353;
int typ[ms];
int lvl[ms];
vector<int> g[ms];
int par[ms];
void dfs1(int u) {
for(int v : g[u]) {
lvl[v] = lvl[u] + 1;
dfs1(v);
}
}
int solve(int u) {
vector<ii> lfts[4];
for(int v : g[u]) {
int x = solve(v);
if(x) lfts[typ[x]].emplace_back(lvl[x], x);
}
if(typ[u]) {
lfts[typ[u]].emplace_back(lvl[u], u);
}
int sob = 0;
int lst = 0;
for(int i = 1; i <= 3; i++) sort(lfts[i].begin(), lfts[i].end());
for(auto [lv, x] : lfts[3]) {
if(lst == 0) {
lst = x;
} else {
if(lvl[lst] == lv) {
par[lst] = x;
par[x] = lst;
lst = 0;
} else {
if(sob != 0 ) {
cout << "NO" << endl;
exit(0);
} else {
sob = lst;
}
lst = x;
}
}
}
if(lst) {
if(sob != 0 ) {
cout << "NO" << endl;
exit(0);
} else {
sob = lst;
}
}
if(lfts[1].size() == lfts[2].size()) {
for(int i = 0; i < lfts[1].size(); i++) {
if(lfts[1][i].first > lfts[2][i].first) {
par[lfts[1][i].second] = lfts[2][i].second;
par[lfts[2][i].second] = lfts[1][i].second;
} else {
cout << "NO" << endl;
exit(0);
}
}
} else if(abs(((int) lfts[1].size()) - ((int) lfts[2].size())) == 1) {
if(sob) {
cout << "NO" << endl;
exit(0);
}
int canSkip = (lfts[1].size() > lfts[2].size()) ? 1 : 2;
if(canSkip == 2) {
reverse(lfts[1].begin(), lfts[1].end());
reverse(lfts[2].begin(), lfts[2].end());
}
int i = 0, j = 0;
while(i < (int) lfts[1].size() && j < (int) lfts[2].size()) {
if(lfts[1][i].first > lfts[2][j].first) {
par[lfts[1][i].second] = lfts[2][j].second;
par[lfts[2][j].second] = lfts[1][i].second;
i++;
j++;
} else {
if(canSkip == 0) {
cout << "NO" << endl;
exit(0);
} else if(canSkip == 1) {
sob = lfts[1][i].second;
i++;
canSkip = 0;
} else if(canSkip == 2) {
sob = lfts[2][j].second;
j++;
canSkip = 0;
}
}
}
if(canSkip == 1) sob = lfts[1].back().second;
else if(canSkip == 2) sob = lfts[2].back().second;
} else {
cout << "NO" << endl;
exit(0);
}
return sob;
}
void solve() {
int n;
cin >> n;
for(int x = 1; x < n; x++) {
int i, p;
cin >> i >> p;
g[p].emplace_back(i);
string s;
cin >> s;
if(s == "Chang") typ[i] = 1;
else if(s == "Duan") typ[i] = 2;
else if(s == "Tong") typ[i] = 3;
}
dfs1(1);
int k = solve(1);
if(k) {
cout << "NO" << endl;
}
cout << "YES" << endl;
for(int i = 2; i <= n; i++) {
if(par[i] > i) cout << i << " " << par[i] << endl;
}
}
int32_t main() {
cin.tie(0); ios::sync_with_stdio(0);
cout << fixed << setprecision(9);
int testes = 1;
// cin >> testes;
int test = 0;
while(testes--) {
// cout << "Case #" << (++test) << ": ";
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 5828kb
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: 3ms
memory: 6256kb
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 2 6 3 10 5 7 8 9
result:
ok Correct.
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 6372kb
input:
2 2 1 Tong
output:
NO YES
result:
wrong output format Extra information in the output file