QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379224#6396. Puzzle: KusabiDestiny#WA 2ms3792kbC++201.6kb2024-04-06 16:40:192024-04-06 16:40:20

Judging History

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

  • [2024-04-06 16:40:20]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3792kb
  • [2024-04-06 16:40:19]
  • 提交

answer

#define TLE ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
#define int ll
const int N=1e6+500;
vector<int >q[N];
int dep[N];
void dfs(int x,int fa){
    for(auto y:q[x]){
        if(y==fa) continue;
        dep[y]=dep[x]+1;
        dfs(y,x);
    }
}
signed main(){
    TLE;
    int n;
    cin>>n;
    vector<int >T,D,C;
    for(int i=1;i<=n;i++){
        int x,y;
        string s;
        cin>>x>>y>>s;
        q[y].push_back(x);
        if(s[0]=='T') {
            T.push_back(x);
        }
        else if(s[0]=='D'){
            D.push_back(x);
        }
        else if(s[0]=='C'){
            C.push_back(x);
        }
    }
    dfs(1,0);
    sort(T.begin(),T.end(),[](const int &x,int &y){
        return dep[x]<dep[y];
    });
    sort(D.begin(),D.end(),[](const int &x,int &y){
        return dep[x]>dep[y];
    });
    sort(C.begin(),C.end(),[](const int &x,int &y){
        return dep[x]>dep[y];
    });
    vector<pair<int ,int >>ans;
    int flag=1;
    if((int)T.size()%2!=0) flag=0;
    if((int)D.size()!=(int)C.size()) flag=0;
    for(int i=0;i<(int)T.size() && flag ;i+=2){
        if(dep[T[i]]!=dep[T[i+1]]) flag=0;
        else ans.push_back({T[i],T[i+1]});
    }
    for(int i=0;i<(int)D.size() && flag;i++){
        if(dep[C[i]]<=dep[D[i]]) flag=0;
        else ans.push_back({C[i],D[i]});
    }
    if(!flag) cout<<"NO\n";
    else {
        cout<<"YES\n";
        for(auto [x,y]:ans){
            cout<<x<<" "<<y<<'\n';
        }
    }
}                         

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3556kb

input:

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

output:

YES
4 5
8 6

result:

ok Correct.

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3792kb

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

result:

wrong answer Edge 3-2 used twice.