QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#108356#6396. Puzzle: KusabicmdgbbWA 2ms3832kbC++144.2kb2023-05-24 19:10:552023-05-24 19:10:58

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-24 19:10:58]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3832kb
  • [2023-05-24 19:10:55]
  • 提交

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