QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#370982#6396. Puzzle: Kusabiricofx#WA 0ms11412kbC++172.1kb2024-03-29 20:36:582024-03-29 20:36:58

Judging History

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

  • [2024-03-29 20:36:58]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:11412kb
  • [2024-03-29 20:36:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define enl putchar('\n')
const int MAXN = 1e5+5;
typedef pair<int,int> pii;
int n,m;
string s;
struct EG{
    int to,nxt;
}e[MAXN];
int head[MAXN],etot;
inline void add(int u,int v){
    e[etot]={v,head[u]};
    head[u]=etot++;
}
vector<int>f[MAXN][3];
int fa[MAXN];
vector<pii>ans;

bool bfs(){
    vector<int>vec;
    queue<int>q;
    q.push(1);
    while(!q.empty()){
        int u=q.front();q.pop();
        vec.push_back(u);
        for(int i=head[u];~i;i=e[i].nxt)
            q.push(e[i].to);
    }
    reverse(vec.begin(),vec.end());
    for(int u:vec){
        // printf("%d %d %d\n",f[u][0].size(),f[u][1].size(),f[u][2].size());
        if((f[u][1].size()>1)||(f[u][2].size()>1)||f[u][0].size() && (f[u][1].size() || f[u][2].size()))
            return !printf("NO\n");
        for(int i=0;i<3;++i)
            if(!f[u][i].empty())
                f[fa[u]][i].push_back(f[u][i][0]);
        if(f[fa[u]][0].size()==2){
            int x=f[fa[u]][0].back();f[fa[u]][0].pop_back();
            int y=f[fa[u]][0].back();f[fa[u]][0].pop_back();
            ans.push_back({x,y});
        }
        if(f[fa[u]][1].size() && f[fa[u]][2].size()){
            ans.push_back({f[fa[u]][1].back(),f[fa[u]][2].back()});
            f[fa[u]][1].pop_back();
            f[fa[u]][2].pop_back();
        }
    }
    if(f[1][0].size()||f[1][1].size()||f[1][2].size())
        return !printf("NO\n");
    return true;
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    memset(head,-1,sizeof(head));
    cin>>n;
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v>>s;
        fa[v]=u;
        add(v,u);
        if(s=="Tong")f[u][0].push_back(u);
        else if(s=="Duan")f[u][1].push_back(u);
        else if(s=="Chang")f[u][2].push_back(u);
    }
    // for(int i=1;i<=n;++i,enl)
    //     for(int j=0;j<3;++j)
    //         // if(!f[i][j].empty())
    //             printf("%d ",f[i][j].size());
    if(bfs()){
        printf("YES\n");
        for(auto [x,y]:ans)
            printf("%d %d\n",x,y);
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 11156kb

input:

8
2 1 -
3 1 -
4 2 Tong
5 2 Tong
6 3 Duan
7 3 -
8 7 Chang

output:

YES
5 4
6 8

result:

ok Correct.

Test #2:

score: 0
Accepted
time: 0ms
memory: 11412kb

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
9 8
3 10
2 6
7 5

result:

ok Correct.

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 11144kb

input:

2
2 1 Tong

output:

YES

result:

wrong answer Only odd number of marked vertices to match.