QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#125441 | #1000. 边三连通分量 | GoatGirl98# | AC ✓ | 68ms | 63992kb | C++14 | 5.7kb | 2023-07-16 18:24:31 | 2023-07-16 18:24:32 |
Judging History
answer
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int rd()
{
int k = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
k = (k << 1) + (k << 3) + c - 48;
c = getchar();
}
return k * f;
}
void wr(int x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
wr(x / 10);
putchar(x % 10 + '0');
}
const int MaxN = 500000, MaxM = 500000;
struct graph_t
{
int cnte;
int head[MaxN + 5], to[MaxM * 2 + 5], next[MaxM * 2 + 5];
graph_t() { cnte = 1; }
inline void addEdge(int u, int v)
{
cnte++;
to[cnte] = v;
next[cnte] = head[u];
head[u] = cnte;
}
};
struct union_find
{
int par[MaxN + 5];
union_find() { memset(par, -1, sizeof par); }
int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }
inline void merge(int u, int v)
{
int p = find(u), q = find(v);
if (p == q)
return;
par[p] += par[q];
par[q] = p;
}
};
int N, M;
graph_t Gr;
struct two_edge_connect
{
int low[MaxN + 5], dfn[MaxN + 5], dfc;
int stk[MaxN + 5], tp;
int bel[MaxN + 5], s;
void dfs(int u, int fe)
{
low[u] = dfn[u] = ++dfc;
stk[++tp] = u;
for (int i = Gr.head[u]; i; i = Gr.next[i])
{
if ((i ^ fe) == 1)
continue;
int v = Gr.to[i];
if (dfn[v] == 0)
{
dfs(v, i);
low[u] = min(low[u], low[v]);
}
else
low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u])
{
s++;
for (;;)
{
int v = stk[tp--];
bel[v] = s;
if (u == v)
break;
}
}
}
inline void init()
{
memset(dfn, 0, sizeof dfn);
dfc = tp = s = 0;
for (int i = 1; i <= N; ++i)
if (dfn[i] == 0)
dfs(i, 0);
}
inline bool isbridge(int u, int v)
{
return bel[u] != bel[v];
}
};
struct three_edge_connect
{
two_edge_connect bcc;
union_find uf;
int low[MaxN + 5], dfn[MaxN + 5], end[MaxN + 5], dfc;
int deg[MaxN + 5];
inline bool insubtree(int u, int v)
{
if (dfn[u] <= dfn[v] && dfn[v] <= end[u])
return true;
else
return false;
}
inline void absorb(vector<int> &path, int u, int w = 0)
{
while (path.empty() == false)
{
int v = path.back();
if (w > 0 && insubtree(v, w) == false)
break;
path.pop_back();
deg[u] += deg[v] - 2;
uf.merge(u, v);
}
}
void dfs(int u, int fe, vector<int> &pu)
{
low[u] = dfn[u] = ++dfc;
for (int i = Gr.head[u]; i; i = Gr.next[i])
{
int v = Gr.to[i];
if (u == v || bcc.isbridge(u, v) == true)
continue;
deg[u]++;
if ((i ^ fe) == 1)
continue;
if (dfn[v] == 0)
{
vector<int> pv;
dfs(v, i, pv);
if (deg[v] == 2)
pv.pop_back();
if (low[v] < low[u])
{
low[u] = low[v];
absorb(pu, u);
pu = pv;
}
else
absorb(pv, u);
}
else
{
if (dfn[v] > dfn[u])
{
absorb(pu, u, v);
deg[u] -= 2;
}
else if (dfn[v] < low[u])
{
low[u] = dfn[v];
absorb(pu, u);
}
}
}
end[u] = dfc;
pu.push_back(u);
}
void init()
{
memset(dfn, 0, sizeof dfn);
memset(deg, 0, sizeof deg);
dfc = 0;
bcc.init();
for (int i = 1; i <= N; ++i)
{
if (dfn[i] == 0)
{
vector<int> pi;
dfs(i, 0, pi);
}
}
}
vector<vector<int>> getall()
{
vector<vector<int>> res(N), ans;
for (int i = 1; i <= N; ++i)
{
int x = uf.find(i);
res[x - 1].push_back(i);
}
for (int i = 0; i < N; ++i)
if (res[i].empty() == false)
ans.push_back(res[i]);
return ans;
}
};
inline void init()
{
N = rd(), M = rd();
for (int i = 1; i <= M; ++i)
{
int u, v;
u = rd() + 1, v = rd() + 1;
Gr.addEdge(u, v);
Gr.addEdge(v, u);
}
}
inline bool cmp(const vector<int> &x, const vector<int> &y) { return x[0] < y[0]; }
inline void solve()
{
static three_edge_connect tcc;
tcc.init();
vector<vector<int>> ans = tcc.getall();
for (int i = 0; i < (int)ans.size(); ++i)
sort(ans[i].begin(), ans[i].end());
sort(ans.begin(), ans.end(), cmp);
wr((int)ans.size()), putchar('\n');
for (int i = 0; i < (int)ans.size(); ++i)
{
int s = (int)ans[i].size();
wr(s), putchar(' ');
for (int j = 0; j < s; ++j)
wr(ans[i][j] - 1), putchar(j == s - 1 ? '\n' : ' ');
}
}
int main()
{
init();
solve();
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 24996kb
input:
4 5 0 2 0 1 3 0 2 1 2 3
output:
3 2 0 2 1 1 1 3
result:
ok OK
Test #2:
score: 0
Accepted
time: 5ms
memory: 25588kb
input:
13 21 4 5 8 7 12 3 3 10 1 5 10 2 0 0 11 4 2 12 9 1 9 0 7 8 7 6 9 1 8 2 12 10 11 0 8 6 3 2 5 9 4 11
output:
6 1 0 3 1 5 9 4 2 3 10 12 2 4 11 1 6 2 7 8
result:
ok OK
Test #3:
score: 0
Accepted
time: 62ms
memory: 62296kb
input:
200000 200000 127668 148778 77100 11865 85144 199231 39485 84917 102044 187263 130204 174776 26220 198288 162188 12078 92196 146334 120537 38083 150353 160479 18707 6545 101149 25450 62271 9177 38892 6454 11709 191939 89247 145109 140599 121858 197410 148980 55975 169098 128576 59852 68224 182347 89...
output:
156853 1 0 43148 1 2 3 4 9 12 13 17 22 36 46 51 52 56 58 61 70 74 77 78 84 98 99 102 117 123 130 133 136 141 161 164 172 174 175 177 184 189 190 192 195 212 220 221 225 232 233 234 246 256 262 267 268 270 272 274 282 283 284 289 295 300 303 305 313 323 358 359 363 366 367 375 384 386 387 392 396 403...
result:
ok OK
Test #4:
score: 0
Accepted
time: 64ms
memory: 59840kb
input:
200000 200000 150762 148756 172967 108322 69862 125085 84513 111056 141009 156725 36311 103205 31879 79919 62895 63377 21697 115522 161610 160423 113104 10277 106927 168428 136657 198931 52292 164110 149020 7038 115111 112823 35584 124385 45429 191603 96444 30523 195578 149089 160105 58103 139792 27...
output:
156961 43040 0 1 3 4 5 8 11 16 21 23 27 33 42 45 50 59 63 67 74 75 87 91 100 108 112 114 116 123 129 134 135 136 138 140 142 145 151 155 156 157 163 164 167 172 173 176 180 184 191 193 197 203 204 205 208 212 219 220 233 246 250 251 262 265 266 267 271 273 278 279 286 291 292 293 297 299 303 306 307...
result:
ok OK
Test #5:
score: 0
Accepted
time: 68ms
memory: 63992kb
input:
200000 200000 53335 120202 193029 92221 8244 61648 50176 7825 97274 91479 85438 76999 26861 80116 162826 198446 160509 95916 143190 116619 121254 192931 121545 132273 149400 91882 97032 5048 179008 82221 187475 70697 159074 65868 158744 94466 120006 170635 36429 162768 61114 17876 131798 188508 1080...
output:
156803 43197 0 1 8 17 25 33 34 44 51 59 60 62 63 65 78 85 90 91 93 95 98 100 104 106 108 117 118 122 141 142 146 149 150 155 156 163 167 168 182 183 185 186 189 197 199 210 224 231 234 235 246 254 256 271 276 287 293 294 296 297 298 301 303 309 311 313 314 320 321 324 338 340 348 353 356 362 363 366...
result:
ok OK
Test #6:
score: 0
Accepted
time: 59ms
memory: 49776kb
input:
127669 148779 124640 77100 11865 117450 85144 68159 104241 39485 76372 84917 102044 56191 43704 26220 67216 31116 75749 123504 12078 92196 70006 15262 100591 74552 120537 38083 19281 29407 18707 6545 101149 25450 62271 9177 38892 6454 11709 119710 60867 89247 14037 9527 121858 66338 112298 81804 795...
output:
85614 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 42056 9 11 12 15 19 21 22 35 36 44 47 50 51 52 62 63 64 65 66 67 73 74 77 78 79 80 84 87 90 91 93 96 97 100 105 111 112 119 123 125 128 130 131 132 136 139 140 144 150 151 155 157 160 161 164 166 172 173 175 176 177 179 181 184 188 190 195 200 212 220 221 22...
result:
ok OK
Test #7:
score: 0
Accepted
time: 46ms
memory: 50488kb
input:
150763 148757 108322 69862 125085 84513 111056 141009 36311 103205 31879 79919 62895 63377 21697 115522 113104 10277 106927 136657 52292 149020 7038 115111 112823 35584 124385 45429 96444 30523 149089 58103 139792 27250 15883 109949 69372 132387 141930 113408 65522 128254 138198 141969 42522 92075 1...
output:
119909 30855 0 1 3 4 5 8 11 12 16 21 23 27 33 42 45 48 50 56 63 67 72 74 75 79 87 89 91 100 108 114 116 118 123 132 134 135 136 138 140 142 144 145 151 155 156 163 164 166 167 172 173 176 184 193 197 204 205 212 217 219 220 226 233 246 251 256 262 266 267 269 271 273 278 279 286 291 292 293 294 297 ...
result:
ok OK
Test #8:
score: 0
Accepted
time: 25ms
memory: 34912kb
input:
53336 120203 26685 8244 50176 7825 31738 24370 25943 19902 11463 26861 29977 26309 14580 31754 1838 29437 30380 12118 51083 31633 1201 18328 26346 5295 48935 19027 31496 19906 41783 5048 47936 16685 5161 34107 15907 28002 332 27672 28930 39563 36429 31696 17876 726 42526 21682 35319 8727 17974 25252...
output:
9550 43787 0 3 4 5 6 8 9 10 11 14 15 17 18 22 23 24 25 26 27 28 29 30 32 33 34 36 37 38 39 40 41 43 44 45 47 48 49 50 51 52 54 55 56 57 58 59 60 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 78 79 80 82 83 84 85 86 88 89 90 91 92 93 94 95 96 97 101 102 103 104 105 106 107 108 109 110 111 112 114 115 ...
result:
ok OK
Test #9:
score: 0
Accepted
time: 10ms
memory: 29924kb
input:
17707 71661 1354 3272 13699 17294 16733 9246 14993 5758 7252 2983 3813 6121 10450 14069 8088 11201 857 4420 12788 2032 11938 1465 10322 15171 14688 1857 2309 2742 2013 13200 14142 16319 10541 1922 10368 1516 7994 9092 3327 5166 13484 2876 15472 13522 15622 13479 3361 15314 15464 14974 17637 7535 435...
output:
354 402 0 12 20 44 81 108 129 345 391 414 430 437 455 489 573 645 665 786 841 866 872 925 945 965 991 1023 1082 1094 1099 1136 1184 1187 1223 1227 1228 1248 1416 1420 1437 1473 1522 1543 1559 1576 1592 1628 1648 1728 1754 1842 1851 1880 1925 1930 1994 2087 2283 2384 2473 2488 2523 2537 2552 2610 268...
result:
ok OK
Test #10:
score: 0
Accepted
time: 0ms
memory: 26156kb
input:
4294 17517 1175 3250 314 389 4272 3633 2938 1831 1307 2818 3321 347 1205 1428 2354 1478 1003 3898 1587 3443 1122 1512 2512 3995 348 3280 2064 1022 1834 2958 4281 1863 689 3613 2115 3708 1645 1488 1601 4181 916 4276 128 2626 4147 2868 87 1411 1802 1451 1254 2010 2936 3120 1065 277 1121 3284 3655 2849...
output:
99 213 0 10 18 27 64 111 133 142 164 227 286 291 324 327 330 336 341 365 374 413 439 442 452 476 486 513 531 536 574 594 638 666 700 717 727 730 757 771 789 797 798 824 837 845 851 900 937 959 1015 1030 1032 1077 1090 1137 1144 1189 1198 1199 1222 1248 1280 1287 1299 1326 1335 1339 1355 1395 1470 14...
result:
ok OK
Test #11:
score: 0
Accepted
time: 15ms
memory: 30332kb
input:
26686 105813 14774 5315 22701 21346 1398 13888 18566 18745 22298 6181 21347 10653 16500 23768 2329 5818 17512 16769 25519 338 12580 3064 19467 21665 3978 13202 23556 25178 195 9695 1472 13111 22925 24074 3026 13281 17666 14469 22007 18680 4159 13152 20431 23814 6671 10788 24433 13211 9794 12608 3264...
output:
553 486 0 39 149 150 162 265 490 498 524 713 943 950 1068 1138 1152 1161 1314 1376 1401 1479 1525 1664 1720 1744 1781 1785 1842 1846 1904 2084 2129 2146 2166 2266 2303 2378 2424 2438 2460 2487 2493 2511 2514 2547 2567 2705 2788 2794 2815 2969 3020 3032 3109 3187 3189 3227 3246 3283 3350 3363 3367 34...
result:
ok OK
Test #12:
score: 0
Accepted
time: 15ms
memory: 30008kb
input:
36033 148595 33366 22486 14414 23855 2694 30361 16352 31902 27993 2048 4707 31743 30610 12884 23278 27069 10529 20914 2030 30015 24554 15673 10184 29423 17825 20383 34077 1181 25518 26129 6355 8810 2857 21736 25108 34280 14992 24299 32649 20227 34529 10407 23194 29913 10451 319 34666 8904 30811 3003...
output:
618 441 0 21 174 262 293 319 502 515 537 605 606 643 799 932 1218 1345 1496 1569 1638 1710 1899 2057 2144 2242 2285 2305 2357 2551 2571 2675 2849 2954 2957 3018 3094 3097 3124 3144 3162 3338 3361 3386 3387 3453 3514 3529 3622 3632 3752 3758 3938 3964 3989 4117 4130 4190 4277 4309 4323 4373 4422 4471...
result:
ok OK
Test #13:
score: 0
Accepted
time: 4ms
memory: 25460kb
input:
14868 57739 5724 2103 9214 3074 2269 531 3811 13162 5199 12632 6337 12078 12592 4977 3553 6975 5063 6622 1221 13056 4252 3705 7547 7879 1702 3685 4058 2503 7540 9423 4280 12228 574 6265 11876 2711 4805 7605 1468 4802 6921 1954 6350 2733 4429 5862 13549 14543 13809 5357 1509 11478 87 2676 6299 7060 1...
output:
387 329 0 9 72 87 95 196 248 275 407 408 458 564 612 717 745 757 775 787 810 1005 1074 1091 1202 1210 1313 1406 1472 1488 1491 1733 1777 1828 1862 1896 2005 2039 2101 2179 2226 2240 2255 2356 2380 2420 2477 2490 2498 2596 2676 2714 2734 2745 2851 2914 2958 2974 2993 3044 3056 3061 3090 3242 3255 328...
result:
ok OK
Test #14:
score: 0
Accepted
time: 1ms
memory: 26196kb
input:
53 43 32 44 25 10 24 49 20 28 28 44 16 12 37 48 46 36 30 47 25 3 17 31 19 17 29 42 25 44 30 3 31 21 2 34 42 12 22 50 12 52 39 10 0 46 29 1 12 21 3 0 11 31 42 25 4 51 26 36 19 48 39 26 5 21 7 41 29 34 38 47 29 8 26 17 42 46 36 20 39 30 13 27 28 31 27 24
output:
45 1 0 1 1 1 2 9 3 25 26 28 31 36 39 42 46 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 27 1 29 1 30 1 32 1 33 1 34 1 35 1 37 1 38 1 40 1 41 1 43 1 44 1 45 1 47 1 48 1 49 1 50 1 51 1 52
result:
ok OK
Test #15:
score: 0
Accepted
time: 0ms
memory: 25900kb
input:
70 21 39 34 29 33 38 53 37 7 47 64 47 17 65 66 60 39 37 47 19 68 14 28 39 41 52 55 0 60 59 16 11 40 11 33 35 26 0 11 24 17 26 43
output:
70 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 ...
result:
ok OK
Test #16:
score: 0
Accepted
time: 0ms
memory: 24688kb
input:
88 139 5 61 52 80 0 17 50 87 62 71 25 69 10 46 44 86 11 38 17 35 73 49 24 47 39 83 8 66 55 56 64 45 83 41 59 35 76 24 2 70 11 77 80 58 84 86 30 50 23 54 36 74 12 10 62 75 33 34 43 28 77 29 10 46 77 33 26 48 32 38 52 79 15 30 25 57 86 0 46 75 81 60 35 83 66 87 25 86 19 85 9 38 15 64 59 82 0 53 40 66 ...
output:
39 50 0 1 2 4 5 6 7 8 9 10 11 15 17 19 20 21 22 23 25 28 30 33 35 36 38 41 44 46 48 49 50 52 56 57 58 61 62 66 70 71 75 76 77 79 80 81 83 85 86 87 1 3 1 12 1 13 1 14 1 16 1 18 1 24 1 26 1 27 1 29 1 31 1 32 1 34 1 37 1 39 1 40 1 42 1 43 1 45 1 47 1 51 1 53 1 54 1 55 1 59 1 60 1 63 1 64 1 65 1 67 1 68...
result:
ok OK
Test #17:
score: 0
Accepted
time: 5ms
memory: 24836kb
input:
53 185 48 40 23 7 45 7 6 42 13 6 45 1 18 28 47 14 11 15 27 9 50 44 23 47 20 27 18 19 2 19 18 49 32 49 9 12 11 0 32 49 22 14 8 48 41 28 30 43 4 21 7 22 28 30 17 11 19 30 44 7 46 8 50 45 35 48 29 47 4 26 16 39 37 25 38 12 19 52 28 41 23 31 33 34 6 15 44 24 0 6 26 22 49 43 4 31 20 38 43 39 41 39 51 40 ...
output:
5 19 0 3 6 8 9 11 12 13 15 17 20 27 35 38 40 42 46 48 51 16 1 4 5 7 14 21 22 23 24 26 29 31 44 45 47 50 1 2 1 10 16 16 18 19 25 28 30 32 33 34 36 37 39 41 43 49 52
result:
ok OK
Test #18:
score: 0
Accepted
time: 1ms
memory: 25832kb
input:
70 252 63 36 64 48 26 34 43 37 30 53 67 64 26 19 25 54 28 44 52 60 4 22 43 48 14 48 12 50 37 23 28 40 48 54 60 23 43 46 7 5 29 39 5 13 57 60 1 23 33 8 59 39 3 29 5 8 34 11 44 40 39 19 40 17 42 48 39 19 49 46 0 48 46 45 57 67 43 60 56 59 32 42 6 54 56 69 23 43 38 65 66 24 0 64 16 10 23 1 4 16 37 49 5...
output:
6 22 0 1 6 14 15 23 25 32 37 42 43 45 46 48 49 51 52 54 57 60 64 67 28 2 3 5 7 8 9 11 12 13 19 21 26 29 30 33 34 35 39 41 50 53 55 56 59 61 62 68 69 17 4 10 16 17 22 24 27 28 31 36 38 40 44 47 58 65 66 1 18 1 20 1 63
result:
ok OK
Test #19:
score: 0
Accepted
time: 1ms
memory: 24688kb
input:
88 390 74 40 14 37 44 66 7 49 12 4 39 48 56 76 46 40 80 30 5 39 52 0 40 79 0 11 34 41 43 80 54 62 61 41 54 37 31 81 59 66 23 59 47 84 16 85 68 29 31 63 4 55 27 5 26 68 14 84 16 34 82 16 62 54 46 15 65 63 58 83 5 36 67 19 65 42 35 25 82 73 55 59 28 36 22 38 46 79 61 34 51 40 69 42 36 5 26 38 86 14 22...
output:
14 5 0 11 45 52 75 7 1 2 30 43 72 73 80 6 3 18 21 58 70 83 9 4 12 23 44 53 55 59 66 71 6 5 27 36 39 48 60 8 6 7 24 28 49 50 64 86 9 8 13 31 42 63 65 67 69 81 6 9 20 33 56 76 77 1 10 7 14 37 47 54 62 78 84 7 15 17 40 46 51 74 79 7 16 34 41 57 61 82 85 5 19 25 32 35 87 5 22 26 29 38 68
result:
ok OK