QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#470585 | #6401. Classic: N Real DNA Pots | UESTC_DebugSimulator# | WA | 1ms | 7828kb | C++17 | 2.9kb | 2024-07-10 15:18:00 | 2024-07-10 15:18:00 |
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], use[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;
for (int i = head[u] ; i ; i = edge[i].next) {
int v = edge[i].to, x;
if (v == p) continue;
x = dfs(v, u);
if (x) a.push_back(x);
}
sort(a.begin(), a.end(), cmp);
int pos = 0, len = a.size(), res = 0;
if (!c[u]) res = u;
while(pos < len) {
vector<int>stk;
stk.push_back(a[pos]);
while(pos + 1 < len && dep[a[pos + 1]] == dep[a[pos]]) {
pos++;
stk.push_back(a[pos]);
}
int tot = stk.size();
for (int i = 0 ; i < tot ; i += 2) ans.push_back({stk[i], stk[i + 1]});
if (tot&1) {
if (res) {
jud = 1;
return 0;
}
res = stk[pos - 1];
}
pos++;
}
return res;
}
int dfs1(int u, int p) {
if (jud) return 0;
vector<int>a[2];
if (c[u] > 0) a[c[u] - 1].push_back(u);
for (int i = head[u] ; i ; i = edge[i].next) {
int v = edge[i].to, x;
if (dep[v] < dep[u] || use[v]) continue;
x = dfs1(v, u);
if (x && c[x] > 0) a[c[x] - 1].push_back(x);
}
sort(a[0].begin(), a[0].end(), cmp);
sort(a[1].begin(), a[1].end(), cmp);
int len0 = a[0].size(), len1 = a[1].size(), res = 0, i, j;
for (i = 0, j = 0 ; i < len0 && j < len1 ; ++i, ++j) {
while(i + 1 < len1 && dep[a[0][i]] <= dep[a[1][j]]) {
if (!res) res = a[0][i];
else {
jud = 1;
return 0;
}
i++;
}
ans.push_back({a[0][i], a[1][j]});
}
if (len0 - i + len1 - j > 1) {
jud = 1;
return 0;
}
if (len0 - i) {
if (res) {
jud = 1;
return 0;
}
res = a[0][i];
}
if (len1 - j) {
if (res) {
jud = 1;
return 0;
}
res = a[1][j];
}
return res;
}
void solve() {
cin >> n;
for (int i = 1 ; 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);
}
dfs(1, 0);
for (auto [x, y] : ans) {
while(x != y) {
if (dep[x] > dep[y]) use[x] = 1, x = fa[x];
else use[y] = 1, y = fa[y];
}
}
use[1] = 1;
for (int i = 1 ; i <= n ; ++i) {
if (use[i]) dfs1(i, 0);
}
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;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 7828kb
input:
4 3 1 2 2 4 3 3 4 1
output:
YES
result:
wrong output format Expected double, but "YES" found