QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#744368 | #5423. Perfect Matching | fengziyang | Compile Error | / | / | C++14 | 2.2kb | 2024-11-13 21:41:08 | 2024-11-13 21:41:10 |
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 now = q.front();
q.pop();
s += du[now];
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] ++;
}
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;
}
详细
answer.code: In function ‘int bfs(int)’: answer.code:18:19: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 18 | for (auto [v , c] : adj[u]) { | ^ answer.code:18:33: error: ‘u’ was not declared in this scope 18 | for (auto [v , c] : adj[u]) { | ^ answer.code: In function ‘int dfs(int, int, int)’: answer.code:30:15: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 30 | for (auto [v , idx] : adj[u]) { | ^ answer.code: In function ‘int main()’: answer.code:85:19: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 85 | for (auto [x , y] : ans) printf ("%d %d\n" , x , y); | ^ answer.code:55:11: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 55 | scanf ("%d" , &T); | ~~~~~~^~~~~~~~~~~ answer.code:59:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 59 | scanf ("%d" , &n); | ~~~~~~^~~~~~~~~~~ answer.code:65:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 65 | scanf ("%d" , &a[i]); | ~~~~~~^~~~~~~~~~~~~~