QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#186323 | #6396. Puzzle: Kusabi | ucup-team228# | WA | 22ms | 11984kb | C++20 | 4.0kb | 2023-09-23 16:59:23 | 2023-09-23 16:59:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int par[N], type[N];
vector<int> g[N];
int timer = 0;
int t_in[N], t_out[N];
int depth[N];
vector<int> level[N];
bool dead[N];
vector<pair<int, int>> ans;
int carry[N];
void dfs1(int v) {
t_in[v] = ++timer;
if (type[v] == 3) {
level[depth[v]].push_back(v);
}
for (int to : g[v]) {
depth[to] = depth[v] + 1;
dfs1(to);
}
t_out[v] = ++timer;
}
bool dfs2(int v) {
vector<pair<int, int>> up;
set<pair<int, int>> down;
for (int to : g[v]) {
if (!dead[to]) {
if (!dfs2(to)) {
return false;
}
if (carry[to]) {
if (type[carry[to]] == 1) {
down.emplace(depth[carry[to]], carry[to]);
} else if (type[carry[to]] == 2) {
up.emplace_back(depth[carry[to]], carry[to]);
} else {
assert(false);
}
}
}
}
if (type[v] == 1) {
down.emplace(depth[v], v);
} else if (type[v] == 2) {
up.emplace_back(depth[v], v);
}
sort(up.begin(), up.end());
vector<int> extra_up, extra_down;
while (!up.empty()) {
auto [dep, u] = up.back();
up.pop_back();
auto it = down.upper_bound({dep, 0});
if (it == down.end()) {
extra_up.push_back(u);
} else {
ans.emplace_back(u, it->second);
down.erase(it);
}
}
for (auto [dep, u] : down) {
extra_down.push_back(u);
}
if (extra_down.size() + extra_up.size() >= 2) {
return false;
} else if (!extra_down.empty()) {
carry[v] = extra_down[0];
} else if (!extra_up.empty()) {
carry[v] = extra_up[0];
}
return true;
}
bool solve(int n) {
dfs1(1);
dead[1] = true;
for (int d = 0; d <= n; d++) {
if (level[d].size() & 1) {
return false;
}
vector<pair<int, int>> cur;
for (int v : level[d]) {
cur.emplace_back(v, v);
}
while (!cur.empty()) {
// for (auto [p, v] : cur) {
// cout << "(" << p << ", " << v << ") ";
// }
// cout << "\n";
vector<pair<int, int>> nxt;
for (int i = 0; i < cur.size(); i++) {
if (i + 1 < cur.size() && cur[i].first == cur[i + 1].first) {
ans.emplace_back(cur[i].second, cur[i + 1].second);
i++;
} else {
if (dead[cur[i].second]) {
return false;
} else {
dead[cur[i].second] = true;
nxt.emplace_back(par[cur[i].second], cur[i].second);
}
}
}
swap(cur, nxt);
}
}
for (int i = 1; i <= n; i++) {
if (dead[i]) {
if (!dfs2(i)) {
return false;
}
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
int n;
cin >> n;
for (int i = 2; i <= n; i++) {
int waste;
string t;
cin >> waste >> par[i] >> t;
if (t == "-") {
type[i] = 0;
} else if (t == "Chang") {
type[i] = 1;
} else if (t == "Duan") {
type[i] = 2;
} else {
type[i] = 3;
}
g[par[i]].push_back(i);
}
if (solve(n)) {
cout << "YES\n";
for (auto [u, v] : ans) {
cout << u << " " << v << "\n";
}
} else {
cout << "NO\n";
}
#ifdef LOCAL
cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9472kb
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: 9408kb
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 3 10 2 6 7 5
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 9764kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 22ms
memory: 11984kb
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.