QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#777842 | #5423. Perfect Matching | haha# | AC ✓ | 434ms | 37356kb | C++14 | 2.9kb | 2024-11-24 10:14:55 | 2024-11-24 10:14:59 |
Judging History
answer
#include <bits/stdc++.h>
#define MAXN ((int) 1e5)
using namespace std;
typedef pair<int, int> pii;
int n, A[MAXN + 10];
vector<pii> ans;
int L, R;
unordered_map<int, int> mpL, mpR;
vector<int> e[MAXN * 2 + 10], v[MAXN * 2 + 10];
int deg[MAXN * 2 + 10], dep[MAXN * 2 + 10];
bool vis[MAXN * 2 + 10];
// BFS 用来统计连通块内边的数量
int bfs(int S) {
int ret = 0;
queue<int> q;
q.push(S); vis[S] = true;
while (!q.empty()) {
int sn = q.front(); q.pop();
ret += deg[sn];
for (int fn : e[sn]) if (!vis[fn]) {
q.push(fn);
vis[fn] = true;
}
}
return ret / 2;
}
// 返回还没有匹配的边
int dfs(int sn, int fa, int from, int d) {
dep[sn] = d;
vector<int> vec;
for (int i = 0; i < e[sn].size(); i++) {
int fn = e[sn][i], idx = v[sn][i];
if (fn == fa) continue;
// 把返祖边和子节点传上来的边都记录下来
if (dep[fn] > 0) {
if (dep[fn] < dep[sn]) vec.push_back(idx);
} else {
int t = dfs(fn, sn, idx, d + 1);
if (t > 0) vec.push_back(t);
}
}
// 把记录下来的边两两匹配
while (vec.size() > 1) {
int x = vec.back(); vec.pop_back();
int y = vec.back(); vec.pop_back();
ans.push_back(pii(x, y));
}
if (vec.size() == 1) {
// 还剩一条边没匹配,把连向父节点的边也用来匹配
assert(from > 0);
ans.push_back(pii(vec.back(), from));
return -1;
} else {
// 连向父节点的边交给父节点匹配
return from;
}
}
void solve() {
mpL.clear(); mpR.clear();
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
mpL[A[i] - i] = 0;
mpR[A[i] + i] = 0;
}
// 离散化
L = R = 0;
for (auto it = mpL.begin(); it != mpL.end(); it++) it->second = ++L;
for (auto it = mpR.begin(); it != mpR.end(); it++) it->second = ++R;
// 建立二分图
for (int i = 1; i <= n * 2; i++) e[i].clear(), v[i].clear();
memset(deg, 0, sizeof(int) * (n * 2 + 3));
for (int i = 1; i <= n; i++) {
int x = mpL[A[i] - i], y = L + mpR[A[i] + i];
e[x].push_back(y); v[x].push_back(i);
e[y].push_back(x); v[y].push_back(i);
deg[x]++; deg[y]++;
}
ans.clear();
memset(vis, 0, sizeof(bool) * (n * 2 + 3));
memset(dep, 0, sizeof(int) * (n * 2 + 3));
// 枚举每个连通块
for (int i = 1; i <= L + R; i++) if (!vis[i]) {
// 奇数条边则无解
if (bfs(i) & 1) { printf("No\n"); return; }
// 偶数条边则构造答案
dfs(i, 0, -1, 1);
}
printf("Yes\n");
for (pii p : ans) printf("%d %d\n", p.first, p.second);
}
int main() {
int tcase; scanf("%d", &tcase);
while (tcase--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 13604kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 6 3 1 4 5 2 Yes 1 3 4 2 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 261ms
memory: 32884kb
input:
10 100000 0 -1 -2 -3 -4 -5 -2 -7 -8 -9 -10 -9 -12 13 14 15 -16 -17 -18 19 20 19 -22 -21 -20 -25 -26 -27 -28 -27 -26 31 30 29 -34 -35 -34 39 38 37 42 41 42 47 44 45 46 49 48 -53 -52 -51 -56 -55 -54 55 56 57 -58 -59 -60 61 62 63 64 65 64 67 66 69 70 73 72 73 74 73 76 75 74 79 80 81 -84 -83 -84 89 86 8...
output:
Yes 78 77 138 137 201 200 242 244 287 289 309 308 315 314 321 320 335 337 380 382 396 395 450 449 459 458 462 461 480 479 515 517 518 520 524 526 554 556 567 566 617 619 660 659 734 736 761 763 788 790 851 853 903 902 933 932 978 977 987 986 1089 1088 1104 1103 1160 1162 1218 1217 1271 1273 1283 128...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 14068kb
input:
10 100 28761184 28761185 28761186 28761187 28761188 28761189 28761190 28761191 -20675012 -20675013 -20675014 -20675015 -20675016 -20675017 -20675018 -20675019 -20675020 -20675021 -20675022 -20675023 -20675024 -20675025 -20675026 -20675027 -20675028 -20675029 -20675030 -20675031 -36758138 -36758139 -...
output:
Yes 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 100 33 32 31 30 29 34 38 37 36 35 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 28 73 72 71 70 69 74 8 7 6 5 4 3 2 1 68 67 66 65 64 62 61 60 59 63 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 257ms
memory: 37356kb
input:
10 100000 -40608960 -40608959 -40608958 -40608957 -40608956 -40608955 -40608954 -40608953 -40608952 -40608951 -40608950 -40608949 -40608948 -40608947 -40608946 -40608945 -40608944 -40608943 -40608942 -40608941 -40608940 -40608939 -40608938 -40608937 -40608936 -40608935 -40608934 -40608933 -40608932 ...
output:
Yes 100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 99953 99952 9...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 434ms
memory: 29624kb
input:
10 100000 0 -1 -2 3 2 5 6 7 -2 1 0 9 12 11 -8 13 8 -7 16 17 -10 19 22 21 22 23 4 -15 -18 -17 -6 -31 -14 25 32 -25 26 27 -32 31 38 -31 -32 -19 -30 -35 46 45 -48 -37 48 41 46 -43 -44 53 56 55 50 -27 52 61 62 -33 -18 19 64 45 46 -57 -8 -25 -26 -11 -22 49 -66 -65 -66 29 78 -15 74 83 12 83 14 85 86 -7 -5...
output:
Yes 89504 28 63463 26518 8564 1121 36811 36817 95315 8931 96991 61541 81303 70110 16772 13611 34736 778 92637 55231 18933 19162 97729 87006 59542 3408 92548 81132 83637 41302 92168 28333 71221 3610 88310 80993 74032 11544 821 940 80608 33052 42619 14756 3199 1661 47380 3633 37677 26691 67617 66364 2...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 142ms
memory: 13780kb
input:
1000 1000 -2 0 3 4 6 7 4 7 6 9 11 9 10 12 16 13 16 17 18 20 19 19 24 22 25 23 28 25 26 27 30 32 31 34 36 37 34 37 37 40 42 43 44 45 43 44 46 45 50 48 51 49 54 55 52 55 54 57 56 61 60 61 64 65 64 67 65 66 67 68 71 73 73 75 76 77 78 75 76 78 82 79 80 81 83 83 87 88 90 89 90 93 92 93 95 94 96 96 100 97...
output:
No No No No No No Yes 14 15 37 36 75 74 113 112 131 130 144 142 152 151 167 165 171 170 185 183 186 184 202 200 207 205 213 212 221 220 245 243 267 266 272 271 278 277 286 284 314 312 330 328 334 333 372 370 377 376 401 400 423 422 426 424 442 440 466 464 476 474 501 499 515 513 559 557 580 578 589 ...
result:
ok 1000 Cases (1000 test cases)