QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#103721 | #6396. Puzzle: Kusabi | tarjen | WA | 8ms | 37012kb | C++17 | 2.0kb | 2023-05-07 13:39:55 | 2023-05-07 13:39:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
vector<pair<int,int>> ans;
void no(){
// for(auto [x,y]:ans)cout<<x<<" "<<y<<"\n";
cout<<"NO\n";exit(0);
}
set<int> s[3][maxn];
vector<int> ve[maxn];
int typ[maxn],dep[maxn];
int n;
void dfs(int x,int h){
// cout<<"x="<<x<<" h="<<h<<"\n";
dep[x]=dep[h]+1;
set<int> now[3];
for(auto it:ve[x]){
dfs(it,x);
for(int z=0;z<3;z++){
for(auto it:s[z][it])now[z].insert(it);
}
}
if(typ[x]!=-1)now[typ[x]].insert(x);
map<int,int> ma;
for(auto it:now[0]){
if(ma.find(dep[it])!=ma.end()){
ans.emplace_back(ma[dep[it]],it);
ma.erase(dep[it]);
}
else ma[dep[it]]=it;
}
int res0=-1;
if(ma.size()>0)res0=ma.begin()->second;
set<pair<int,int>> s1,s2;
for(auto it:now[1])s1.insert({dep[it],it});
for(auto it:now[2])s2.insert({dep[it],it});
auto it2=s1.end();
while(it2!=s1.begin()){
it2--;
auto [d,x]=*it2;
auto fd=s2.lower_bound({d+1,0});
if(fd==s2.end()){
it2--;continue;
}
ans.emplace_back(x,fd->second);
s2.erase(fd);
it2=s1.erase(it2);
}
// if((int)ma.size()+(int)s1.size()+(int)s2.size()>1)no();
if(res0!=-1)s[0][x].insert(res0);
if(!s1.empty())s[1][x].insert(s1.begin()->second);
if(!s2.empty())s[2][x].insert(s2.begin()->second);
// if(x==1){
// if((int)ma.size()+(int)s1.size()+(int)s2.size()>0)no();
// }
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
memset(typ,-1,sizeof(typ));
cin>>n;
for(int i=2;i<=n;i++){
int x;cin>>x>>x;
string s;
cin>>s;
ve[x].push_back(i);
if(s=="Tong")typ[i]=0;
if(s=="Duan")typ[i]=1;
if(s=="Chang")typ[i]=2;
}
dfs(1,0);
cout<<"YES\n";
for(auto [x,y]:ans)cout<<x<<" "<<y<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 36940kb
input:
8 2 1 - 3 1 - 4 2 Tong 5 2 Tong 6 3 Duan 7 3 - 8 7 Chang
output:
YES 4 5 6 8
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 3ms
memory: 36952kb
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 3 10 8 9 2 6 7 5
result:
ok Correct.
Test #3:
score: -100
Wrong Answer
time: 8ms
memory: 37012kb
input:
2 2 1 Tong
output:
YES
result:
wrong answer Only odd number of marked vertices to match.