QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#471131 | #6396. Puzzle: Kusabi | UESTC_DebugSimulator | WA | 25ms | 9860kb | C++17 | 2.7kb | 2024-07-10 18:27:37 | 2024-07-10 18:27:37 |
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) 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) {
if (!x || !y) cout << x << ' ' << y << '\n';
}
for (auto [x, y] : ans) {
cout << x << ' ' << y << '\n';
}
}
signed main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7716kb
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: 1ms
memory: 7764kb
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: 1ms
memory: 7764kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 25ms
memory: 9860kb
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 45174 0 18979 0 13971 0 22404 0 42118 0 14245 0 17834 0 41090 0 22026 0 15025 0 26255 0 50530 0 18068 0 48362 0 16687 0 12987 0 13587 0 10538 0 2146 0 37914 0 6641 0 19369 0 16565 0 44646 0 68138 0 37266 0 51154 0 19356 0 34890 0 31311 0 47695 0 2220 0 31623 0 43936 0 47300 0 87667 0 25109 0 163...
result:
wrong answer Integer 0 violates the range [1, 100000]