QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#471147 | #6396. Puzzle: Kusabi | UESTC_DebugSimulator | WA | 22ms | 9624kb | C++17 | 2.6kb | 2024-07-10 18:34:46 | 2024-07-10 18:34:47 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lowbit(i) (i&-i)
#define rand() (myrand())
using namespace std;
mt19937 myrand(time(0));
const int maxn = 2e5 + 5;
int n, _, head[maxn], cnt;
int c[maxn], dep[maxn], jud, fa[maxn];
string ty;
vector<pair<int, int> >ans;
struct node{
int next, to;
}edge[maxn<<1];
void addedge(int from, int to) {
edge[++cnt].next = head[from];
edge[cnt].to = to;
head[from] = cnt;
}
bool cmp(int x, int y) {return dep[x] < dep[y];}
int dfs(int u, int p) {
if (jud) return 0;
dep[u] = dep[p] + 1;
vector<int>a[3];
if (c[u] != -1) a[c[u]].push_back(u);
for (int i = head[u] ; i ; i = edge[i].next) {
int v = edge[i].to;
if (v == p) continue;
int x = dfs(v, u);
if (c[x] != -1) a[c[x]].push_back(x);
}
sort(a[0].begin(), a[0].end(), cmp);
sort(a[1].begin(), a[1].end(), cmp);
sort(a[2].begin(), a[2].end(), cmp);
int len0 = a[0].size(), len1 = a[1].size(), len2 = a[2].size(), res = 0, cnt = 0, pos = 0;
while(pos < len0) {
vector<int>stk;
stk.push_back(a[0][pos]);
while(pos + 1 < len0 && dep[a[0][pos + 1]] == dep[a[0][pos]]) {
pos++;
stk.push_back(a[0][pos]);
}
int tot = stk.size();
if (tot >= 2) for (int i = 0 ; i < tot ; i += 2) {
if (!stk[i] || !stk[i + 1]) continue;
ans.push_back({stk[i], stk[i + 1]});
}
if (tot&1) {
cnt++;
res = stk[tot - 1];
}
pos++;
}
int i, j;
if (len1 < len2) {
for (i = len2 - 1, j = len1 - 1 ; i >= 0 && j >= 0 ; --i) {
if (dep[a[1][j]] > dep[a[2][i]]) {
ans.push_back({a[1][j], a[2][i]});
j--;
}
else {
res = a[2][i];
cnt++;
}
}
if (!i) res = a[2][i], cnt++;
if (!j) res = a[1][j], cnt++;
}
else {
for (i = 0, j = 0 ; i < len1 && j < len2 ; ++i) {
if (dep[a[1][i]] > dep[a[2][j]]) {
ans.push_back({a[1][i], a[2][j]});
j++;
}
else {
res = a[1][i];
cnt++;
}
}
if (i == len1 - 1) res = a[1][i], cnt++;
if (j == len2 - 1) res = a[2][j], cnt++;
}
if (cnt > 1) {
jud = 1;
return 0;
}
return res;
}
void solve() {
cin >> n;
for (int i = 0 ; i <= n ; ++i) c[i] = -1;
for (int i = 1 ; i < n ; ++i) {
int x, p;
cin >> x >> p >> ty;
fa[x] = p;
if (ty[0] != '-') {
if (ty[0] == 'T') c[x] = 0;
if (ty[0] == 'C') c[x] = 1;
if (ty[0] == 'D') c[x] = 2;
}
addedge(x, p);
addedge(p, x);
}
if (dfs(1, 0)) jud = 1;
if (jud) {
cout << "NO" << '\n';
return;
}
cout << "YES" << '\n';
for (auto [x, y] : ans) {
cout << x << ' ' << y << '\n';
}
}
signed main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5748kb
input:
8 2 1 - 3 1 - 4 2 Tong 5 2 Tong 6 3 Duan 7 3 - 8 7 Chang
output:
YES 8 6 5 4
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 0ms
memory: 7800kb
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 9 8 10 3 6 2 5 7
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 7960kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 22ms
memory: 9624kb
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 78961 61327 79617 28763 40169 25684 49361 25045 60228 24156 97603 50185 72206 56901 41848 10579 76635 73900 73042 50152 47346 25325 91464 63312 91034 79886 53651 27084 20428 10551 98200 36927 80157 69283 78977 68167 33135 10332 87866 40003 10826 10300 83126 81993 61240 63025 51469 32742 33688 26...
result:
wrong answer Vertex 9979 used twice.