QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#243684 | #6396. Puzzle: Kusabi | ucup-team1198# | WA | 2ms | 6116kb | C++20 | 5.7kb | 2023-11-08 15:50:06 | 2023-11-08 15:50:07 |
Judging History
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.