QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#108356 | #6396. Puzzle: Kusabi | cmdgbb | WA | 2ms | 3832kb | C++14 | 4.2kb | 2023-05-24 19:10:55 | 2023-05-24 19:10:58 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
int n;
const int N=100010;
int d[N],ver[N*2],Next[N*2],tot,head[N];
int q[N];
struct aa
{
int x,y;
} T[N],C[N],D[N];
int t1=0,c1=0,d1=0;
int ans[N];
int sum=0,p[N];
void add(int x,int y)
{
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
void ds()
{
cin>>n;
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
char s[10];
scanf("%s",s);
if(s[0]=='_')q[x]=1;
else if(s[0]=='C')q[x]=2;
else if(s[0]=='D')q[x]=3;
else if(s[0]=='T')q[x]=4;
add(y,x);
add(x,y);
}
}
void jia(int x)
{
if(q[x]==2)
{
c1++;
C[c1].x=d[x];
C[c1].y=x;
}
if(q[x]==3)
{
d1++;
D[d1].x=d[x];
D[d1].y=x;
}
if(q[x]==4)
{
t1++;
T[t1].x=d[x];
T[t1].y=x;
}
}
bool com(aa x,aa y)
{
return x.x<y.x;
}
int tong()
{
sort(T+1,T+1+t1,com);
int md=0,w;
for(int i=1;i+1<=t1;i+=2)
{
if(T[i].x==T[i+1].x)
{
sum++;
p[sum]=T[i].y;
sum++;
p[sum]=T[i+1].y;
}
else
{
if(md==0)
{
md=T[i].y;
i--;
}
else return -1;
}
w=i;
}
if(t1%2&&w+1!=t1)
{
if(md==0)
{
md=T[t1].y;
}
else return -1;
}
return md;
}
int cd()
{
sort(D+1,D+1+d1,com);
sort(C+1,C+1+c1,com);
if(c1==d1)
{
for(int i=1;i<=c1;i++)
{
if(C[i].x>D[i].x)
{
sum++;
p[sum]=C[i].y;
sum++;
p[sum]=D[i].y;
}
else return -1;
}
return 0;
}
else if(c1-d1==1)
{
int md=0;
for(int i=1,j=1;j<=d1;j++,i++)
{
if(C[i].x>D[j].x)
{
sum++;
p[sum]=C[i].y;
sum++;
p[sum]=D[j].y;
}
else
{
if(md==0)
{
md=C[i].y;
j--;
}
else return -1;
}
}
if(md==0)md=C[c1].y;
return md;
}
else if(d1-c1==1)
{
int md=0;
for(int i=c1,j=d1;i>=1;i--,j--)
{
if(C[i].x>D[j].x)
{
sum++;
p[sum]=C[i].y;
sum++;
p[sum]=D[j].y;
}
else
{
if(md==0)
{
md=D[j].y;
i++;
}
else return -1;
}
}
if(md==0)md=D[1].y;
return md;
}
else return -1;
}
void qk()
{
t1=0;
c1=0;
d1=0;
}
int dfs(int x)
{
//cout<<x<<endl<<endl;
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(d[y]&&d[y]<d[x])continue;
d[y]=d[x]+1;
if(dfs(y)==-1)
{
return -1;
}
}
qk();
for(int i=head[x];i;i=Next[i])
{
if(d[ver[i]]<d[x])continue;
jia(ans[ver[i]]);
//if(x==2)cout<<ans[ver[i]]<<endl;
}
jia(x);
int md=tong();
if(x==1&&md!=0)return -1;
if(md==-1)
{
//cout<<x<<endl<<t1<<endl;
return -1;
}
else
{
ans[x]=md;
//if(x==5)cout<<"5: "<<ans[x]<<endl;
}
md=cd();
if(md==-1)
{
return -1;
}
else if(md!=0&&ans[x])return -1;
else if(md)ans[x]=md;
if(x==1&&md!=0)return -1;
return 0;
}
void print()
{
for(int i=1;i<=sum;i+=2)
{
printf("%d %d\n",p[i],p[i+1]);
}
}
int main()
{
ds();
d[1]=1;
if(dfs(1)==-1)
{
printf("NO");
}
else
{
printf("YES\n");
print();
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3832kb
input:
8 2 1 - 3 1 - 4 2 Tong 5 2 Tong 6 3 Duan 7 3 - 8 7 Chang
output:
YES 8 6
result:
wrong output format Unexpected end of file - int32 expected