QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#744382#5423. Perfect MatchingfengziyangWA 0ms14136kbC++172.2kb2024-11-13 21:43:582024-11-13 21:43:59

Judging History

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

  • [2024-11-13 21:43:59]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:14136kb
  • [2024-11-13 21:43:58]
  • 提交

answer

#include <bits/stdc++.h>
#define PII pair<int , int>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int N = 3e5 + 5;
int cnt , du[N] , a[N] , n , dep[N] , vis[N];
map<int , int> idl , idr;
vector<PII> adj[N] , ans;
queue<int> q;
int bfs (int x) {
    q.push(x);
    int s = 0;
    vis[x] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        s += du[u];
        for (auto [v , c] : adj[u]) {
            if (!vis[v]) {
                vis[v] = 1;
                q.push(v);
            }
        }
    }
    return s / 2;
}
int dfs (int u , int fa , int lst) {
    dep[u] = dep[fa] + 1;
    vector<int> V;
    for (auto [v , idx] : adj[u]) {
        if (v == fa) continue;
        if (dep[v] > 0) {
            if (dep[u] > dep[v]) V.push_back(idx);
        }
        else {
            int t = dfs (v , u , idx);
            if (t > 0) V.push_back(t);
        }
    }
    while (V.size() > 1) {
        int x = V.back ();
        V.pop_back();
        int y = V.back();
        V.pop_back();
        ans.emplace_back(x , y);
    }
    if (V.size() == 1) {
        ans.emplace_back(V[0] , lst);
        return -1;
    }
    return lst;
}
int main () {
    int T;
    scanf ("%d" , &T);
    while (T --) {
        idl.clear() , idr.clear();
        cnt = 0;
        scanf ("%d" , &n);
        fu (i , 0 , n << 1) {
            dep[i] = du[i] = vis[i] = 0;
            adj[i].clear();
        }
        fu (i , 1 , n) {
            scanf ("%d" , &a[i]);
            if (idl[i - a[i]] == 0) idl[i - a[i]] = ++cnt;
            if (idr[i + a[i]] == 0) idr[i + a[i]] = ++cnt;
            int x = idl[i - a[i]] , y = idr[i + a[i]];
            adj[x].emplace_back(y , i);
            adj[y].emplace_back(x , i);
            du[x] ++ , du[y] ++;
        }
        ans.clear();
        int flg = 0;
        fu (i , 1 , cnt) {
            if (!vis[i]) {
                if (bfs (i) & 1) {
                    puts ("No");
                    flg = 1;
                }
                dfs (i , 0 , -1);
            }
        }
        if (flg) continue;
        puts ("Yes");
        for (auto [x , y] : ans) printf ("%d %d\n" , x , y);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 14136kb

input:

3
6
14 22 33 11 25 36
4
100 10 98 12
4
1 3 5 7

output:

Yes
4 1
5 2
6 3
Yes
3 1
4 2
No
No
No
No

result:

wrong output format Extra information in the output file (test case 3)