QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379224 | #6396. Puzzle: Kusabi | Destiny# | WA | 2ms | 3792kb | C++20 | 1.6kb | 2024-04-06 16:40:19 | 2024-04-06 16:40:20 |
Judging History
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.