QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#301861#6396. Puzzle: KusabiSaanteye#WA 37ms15496kbC++171.8kb2024-01-10 13:28:412024-01-10 13:28:42

Judging History

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

  • [2024-01-10 13:28:42]
  • 评测
  • 测评结果:WA
  • 用时:37ms
  • 内存:15496kb
  • [2024-01-10 13:28:41]
  • 提交

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;
}

详细

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.