QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#528581 | #6396. Puzzle: Kusabi | megumi# | WA | 1ms | 9784kb | C++14 | 4.3kb | 2024-08-23 16:28:58 | 2024-08-23 16:28:59 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
inline int read() {
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
f = (c == '-') ? -1 : 1, c = getchar();
while (c >= '0' && c <= '9')
x = x * 10 + c - 48, c = getchar();
return f * x;
}
const int N = 1e5 + 10;
int head[N], cnt;
struct edge {
int to, next;
} edge[N << 2];
void add(int u, int v) {
edge[++cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
}
int dep[N], cc[N],
tt[N]; // 每个点的深度 每个点传上来的数据的深度 传上来的数据对应的点的编号
char a[N];
pair<char, int> P[N];
pair<int, int> ans[N];
int tr, mx;
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1;
vector<pair<int, int>> vv[3]; // 分别存子树传上来的长短同
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (v == fa)
continue;
dfs(v, u);
if (!tr)
return;
if (a[v] == 'C')
vv[0].push_back({cc[v], tt[v]});
else if (a[v] == 'D')
vv[1].push_back({cc[v], tt[v]});
else if (a[v] == 'T')
vv[2].push_back({cc[v], tt[v]});
}
if (a[u] == 'C')
vv[0].push_back({dep[u], u});
else if (a[u] == 'D')
vv[1].push_back({dep[u], u});
else if (a[u] == 'T')
vv[2].push_back({dep[u], u});
sort(vv[0].begin(), vv[0].end());
sort(vv[1].begin(), vv[1].end());
sort(vv[2].begin(), vv[2].end());
int len0 = vv[0].size(), len1 = vv[1].size(), len2 = vv[2].size();
int flag = -1;
if ((len0 + len1) % 2 + len2 % 2 == 2) {
tr = 0;
return;
}
if (abs(len0 - len1) >= 2) {
tr = 0;
return;
}
a[u] = '-';
for (int i = 0; i < len2; i += 2) {
if (i == len2 - 1 || vv[2][i].first != vv[2][i + 1].first) {
if (flag != -1) {
tr = 0;
return;
}
flag = i, i--;
continue;
}
ans[++mx] = {vv[2][i].second, vv[2][i + 1].second};
}
if (len2 % 2 == 0 && flag != -1) {
tr = 0;
return;
} else if (flag != -1) {
a[u] = 'T';
cc[u] = vv[2][flag].first;
tt[u] = vv[2][flag].second;
}
if (len0 == len1) {
for (int i = 0; i < len0; i++) {
if (vv[0][i].first <= vv[1][i].first) {
tr = 0;
return;
}
ans[++mx] = {vv[0][i].second, vv[1][i].second};
}
return;
}
if (len0 > len1) { // 长多
int r = 0;
a[u] = 'C';
int flag = len0 - 1;
for (int i = 0; i < len1; i++) {
while (vv[0][r].first <= vv[1][i].first && r < len0) {
r++;
flag = r;
if (r == len0) {
tr = 0;
return;
}
}
ans[++mx] = {vv[0][i].second, vv[1][r].second};
r++;
if (r > len0) {
tr = 0;
return;
}
}
cc[u] = vv[0][flag].first;
tt[u] = vv[0][flag].second;
}
else { // 短多
a[u] = 'D';
int r = len1 - 1, flag = 0;
for (int i = len0 - 1; i >= 0; i--) {
if (r == -1) {
tr = 0;
return;
}
while (vv[0][i].first <= vv[1][r].first) {
flag = r;
r--;
if (r == -1) {
tr = 0;
return;
}
}
ans[++mx] = {vv[0][i].second, vv[1][r].second};
r--;
}
cc[u] = vv[1][flag].first;
tt[u] = vv[1][flag].second;
}
}
signed main() {
int n;
n = read();
string s;
tr = 1;
for (int i = 1; i < n; i++) {
int u = read(), fa = read();
cin >> s;
add(fa, u);
a[u] = s[0];
}
dep[1] = 1;
dfs(1, 0);
if (!tr)
cout << "NO\n";
else {
cout << "YES\n";
for (int i = 1; i <= mx; i++) {
cout << ans[i].first << ' ' << ans[i].second << "\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9784kb
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: 1ms
memory: 9772kb
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 6 2 5 7
result:
ok Correct.
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 7724kb
input:
2 2 1 Tong
output:
YES
result:
wrong answer Only odd number of marked vertices to match.