QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#470609 | #6396. Puzzle: Kusabi | UESTC_xxx# | WA | 2ms | 9964kb | C++20 | 1.6kb | 2024-07-10 15:25:57 | 2024-07-10 15:25:59 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
#define ll long long
#define lowbit(x) x&(-x)
using namespace std;
int n,s[500005],cy[500005],cx[500005],tot;
vector<int>e[500005];
struct node{
int d,tp,id;
}p[500005],a[500005];
bool cmp(node a,node b){
if(a.d==b.d) return a.tp>b.tp;
return a.d<b.d;
}
void dfs(int u,int dp){
p[u].id=u;
p[u].d=dp;
s[u]=(p[u].tp!=0);
for(int i=0;i<e[u].size();++i){
int v=e[u][i];
dfs(v,dp+1);
s[u]+=s[v];
}
int cnt=0;
if(p[u].tp) cnt++,a[cnt]=p[u];
for(int i=0;i<e[u].size();++i){
int v=e[u][i];
if(s[v]%2) cnt++,a[cnt]=p[v];
}
sort(a+1,a+cnt+1,cmp);
int f=0;
for(int i=1;i<=cnt;++i){
if(a[i].tp==1){
if(a[i+1].tp==1&&i!=cnt){
tot++,cx[tot]=a[i].id,cy[tot]=a[i+1].id;
i++;
}
else f++,p[u]=a[i];
}
}
queue<node>q;
for(int i=1;i<=cnt;++i){
if(a[i].tp==1) continue;
if(a[i].tp==3){
q.push(a[i]);
}
if(a[i].tp==2){
if(!q.size()) f++,p[u]=a[i];
else{
node g=q.front();
tot++,cx[tot]=g.id,cy[tot]=a[i].id;
q.pop();
}
}
}
while(q.size()){
f++,p[u]=q.front();
q.pop();
}
if(f>1) printf("NO"),exit(0);
}
int main(){
scanf("%d",&n);
for(int i=2;i<=n;++i){
int x,y;
char s[6];
scanf("%d%d%s",&x,&y,s);
e[y].push_back(x);
if(s[0]=='T') p[x].tp=1;
if(s[0]=='C') p[x].tp=2;
if(s[0]=='D') p[x].tp=3;
}
dfs(1,0);
printf("YES\n");
for(int i=1;i<=tot;++i){
printf("%d %d\n",cx[i],cy[i]);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 9964kb
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: 2ms
memory: 9960kb
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 3 10 8 9 2 6 7 5
result:
ok Correct.
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 8136kb
input:
2 2 1 Tong
output:
YES
result:
wrong answer Only odd number of marked vertices to match.