QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#301861 | #6396. Puzzle: Kusabi | Saanteye# | WA | 37ms | 15496kb | C++17 | 1.8kb | 2024-01-10 13:28:41 | 2024-01-10 13:28:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> PII;
const int N = 1e5 + 10, mod = 998244353;
int st[N];
vector<int>q[N];
vector<int>tot[N][3];
void dfs(int x,int dep)
{
if(st[x]){
tot[dep][st[x]-1].push_back(x);
}
for(auto w:q[x]){
dfs(w,dep+1);
}
}
void solve() {
int n;
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
string s;
cin>>s;
q[v].push_back(u);
if(s=="-"){
st[u]=0;
}else if(s=="Tong"){
st[u]=1;
}else if(s=="Duan"){
st[u]=2;
}else{
st[u]=3;
}
}
dfs(1,1);
bool ok=true;
vector<PII>res;
for(int i=1;i<=n;i++){
if(tot[i][0].size()&1){
ok=false;
break;
}
while(tot[i][0].size()){
int p1=tot[i][0].back();
tot[i][0].pop_back();
int p2=tot[i][0].back();
tot[i][0].pop_back();
res.push_back({p1,p2});
}
}
int t=2;
for(int i=1;i<=n;i++){
while(tot[i][1].size()){
int p1=tot[i][1].back();
tot[i][1].pop_back();
while(t<=n&&tot[t][2].empty()){
t++;
}
if(tot[t][2].empty()){
ok=false;
break;
}
int p2=tot[t][2].back();
tot[t][2].pop_back();
res.push_back({p1,p2});
}
}
if(ok){
cout<<"YES\n";
for(auto w:res){
cout<<w.first<<' '<<w.second<<'\n';
}
}else{
cout<<"NO\n";
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12816kb
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: 2ms
memory: 12816kb
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 7 6 2 5 3 10
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 5ms
memory: 12844kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 37ms
memory: 15496kb
input:
100000 2 1 Duan 3 1 Duan 4 3 - 5 4 Duan 6 3 - 7 4 Duan 8 4 - 9 8 - 10 7 Duan 11 9 - 12 7 Duan 13 7 Duan 14 8 Duan 15 13 - 16 10 Duan 17 11 Duan 18 12 - 19 1 Duan 20 5 Duan 21 4 Duan 22 14 Duan 23 16 - 24 22 Duan 25 16 Duan 26 13 - 27 13 - 28 17 - 29 5 Duan 30 22 - 31 23 - 32 9 Duan 33 5 - 34 30 Duan...
output:
YES 78961 61327 79617 28763 59851 14132 31315 3156 78400 3283 83333 28194 95031 79799 27446 24772 15911 3681 58699 33789 85932 19874 69010 8241 8873 7241 69894 52589 41090 93895 53651 27084 55428 52038 28273 27407 58447 22579 18084 7965 14566 8063 41654 24933 21793 6310 76595 61255 75085 15407 87751...
result:
wrong answer Edge 1134-154 used twice.