QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#744382 | #5423. Perfect Matching | fengziyang | WA | 0ms | 14136kb | C++17 | 2.2kb | 2024-11-13 21:43:58 | 2024-11-13 21:43:59 |
Judging History
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)