QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#378854#6396. Puzzle: KusabiBadMiiilk_#WA 27ms26012kbC++233.5kb2024-04-06 14:58:372024-04-06 14:58:46

Judging History

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

  • [2024-04-06 14:58:46]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:26012kb
  • [2024-04-06 14:58:37]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ld long double
#define i64 __int128
#define PII pair<int,int>
#define endl '\n'
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
//cout<<setiosflags(ios::fixed)<<setprecision(K);
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};
const double eps = 1e-9; 
const double PI = acos(-1.0);
const int INF = 1e9 + 7;
const int mod = 998244353;
const int N = 2e5 + 10,M = N << 1;

void solve(){
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    vector<int> a(n + 1);
    for(int i = 2;i <= n;i ++){
        int x,y;
        string op;
        cin >> x >> y >> op;
        g[x].push_back(y);
        g[y].push_back(x);
        if(op[0] == '-'){
            a[i] = 0;
        }else if(op[0] == 'T'){
            a[i] = 1;
        }else if(op[0] == 'D'){
            a[i] = 2;
        }else{
            a[i] = 3;
        }
    }   
    vector<int> dep(n + 1);
    // dep[1] = 1; 
    // vector<vector<vector<PII>>> cnt(n+1,vector<vector<PII>>(4)); 
    bool ok = 1;
    vector<PII> ans;
    queue<PII> q;
    vector<vector<priority_queue<PII>>> cnt(n+1,vector<priority_queue<PII>>(4));
    function<void(int,int)> dfs = [&](int x,int fa){
        if(ok == 0) return;
        dep[x] = dep[fa] + 1;
        for(auto item : g[x]){
            if(item == fa) continue;
            dfs(item,x);
            for (int i = 1; i < 4; i++)
            {
                while (!cnt[item][i].empty())
                {
                    cnt[x][i].push(cnt[item][i].top());
                    cnt[item][i].pop();
                }
            }
        }
        
        if (a[x]!=0){
            cnt[x][a[x]].push({dep[x],x});
        }
        queue<PII> q;
        while (cnt[x][1].size()>1)
        {
            auto [x1,idx1] = cnt[x][1].top();
            cnt[x][1].pop();
            auto [x2,idx2] = cnt[x][1].top();
            if (x1!=x2){
                // cnt[x][1].pop();
                q.push({x1,idx1});
            }else {
                ans.push_back({idx1,idx2});
                cnt[x][1].pop();
                // cnt[x][].pop();
            }
        }
        // if (q.size()+cnt[x][1].size()>1){
        //     ok =0 ;
        // }
        while (!q.empty())
        {
            cnt[x][1].push(q.front());
            q.pop();            
        }
        queue<PII> q2;
        while (!cnt[x][2].empty()&&!cnt[x][3].empty())
        {
            auto [x1,idx1] = cnt[x][2].top();
            auto [x2,idx2] = cnt[x][3].top();
            if (x1>=x2){
                q2.push({x1,idx1});
                cnt[x][2].pop();
            }else {
                cnt[x][2].pop();
                cnt[x][3].pop();
                ans.push_back({idx1,idx2});
            }
        }
        while (!q2.empty())
        {
            cnt[x][2].push(q2.front());
            q2.pop();
        }
        if (cnt[x][1].size()+cnt[x][2].size()+cnt[x][3].size()>1){
            ok =0;
        }
    };
    dfs(1,0);
    for(int i = 1;i <= 3;i ++){
        if(cnt[1][i].size() != 0){
            cout << "NO" << endl;
            return;
        }
    }
    if (ok){
        cout << "YES\n";
        for(auto [x,y]:ans){
            cout << x<< ' '<< y<<'\n';
        }
    }else {
        cout << "NO\n";
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.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: 3792kb

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: 0ms
memory: 3584kb

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

result:

ok Correct.

Test #3:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 27ms
memory: 26012kb

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:

NO

result:

wrong answer Jury has answer but participant has not.