QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#328581 | #1844. Cactus | LYT0122 | AC ✓ | 166ms | 101012kb | C++14 | 3.2kb | 2024-02-15 21:29:36 | 2024-02-15 21:29:37 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long int ll;
const int N=1e6+9,INF=1e9;
const double eps=1e-5;
typedef pair <int,int> PII;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<'0' || c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0' && c<='9') {x=x*10+c-48,c=getchar();}
return x*f;
}
inline ll readll()
{
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0' && c<='9') {x=x*10+c-48,c=getchar();}
return x*f;
}
struct node{
int to,nxt;
} edge[N];
int n,m,tot,d[N],head[N],ans[N],cnt,dfn[N],low[N],idx,st[N],top,IDX,tmp[N];
bool vis[N];
vector <int> g[N],e[N];
void addedge(int u,int v)
{
edge[++tot].to=v,edge[tot].nxt=head[u],head[u]=tot;
}
void del(int u)
{
vis[u]=true,d[u]=0,ans[++cnt]=u;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(vis[v]==false) d[v]^=1;
}
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(d[v]) del(v);
}
}
void tarjan(int u,int fa)
{
dfn[u]=low[u]=++idx,st[++top]=u;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(dfn[v]==0)
{
tarjan(v,u),low[u]=min(low[u],low[v]);
if(dfn[u]<=low[v])
{
e[++IDX].push_back(u),e[u].push_back(IDX);
while(st[top+1]!=v) e[IDX].push_back(st[top]),e[st[top]].push_back(IDX),top--;
}
}
else if(v!=fa) low[u]=min(low[u],dfn[v]);
}
}
void dfs(int u,int fa)
{
vis[u]=true;
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(vis[v]==false) dfs(v,u);
}
if(u<=n) return;
int len=0,pos=0;
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(v==fa) pos=i;
}
for(int i=pos;i<e[u].size();i++) tmp[++len]=e[u][i];
for(int i=0;i<pos;i++) tmp[++len]=e[u][i];
for(int i=2;i<=len;i++) ans[++cnt]=tmp[i]+(i&1)*n;
if(len&1) ans[++cnt]=tmp[2]+n,ans[++cnt]=tmp[len];
else ans[++cnt]=tmp[2]+n,ans[++cnt]=tmp[len]+n;
}
int main()
{
#ifdef FILEIO
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
addedge(u,v),addedge(v,u);
d[u]^=1,d[v]^=1;
}
for(int i=1;i<=n;i++)
if(d[i]) del(i);
for(int u=1;u<=n;u++)
{
if(vis[u]) continue;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(vis[v]==false) g[u].push_back(v);
}
}
ans[++cnt]=-1;
IDX=n;
for(int i=1;i<=n;i++)
if(dfn[i]==0) tarjan(i,0);
for(int i=1;i<=n;i++) vis[i]=false;
for(int i=1;i<=n;i++)
if(vis[i]==false) dfs(i,0),ans[++cnt]=i;
cout<<"0 "<<cnt<<'\n';
for(int i=1;i<=cnt;i++)
{
if(ans[i]==-1) puts("2");
else cout<<"1 "<<ans[i]<<'\n';
}
cerr<<endl<<1e3*clock()/CLOCKS_PER_SEC<<"ms";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 9ms
memory: 59560kb
input:
3 3 1 2 1 3 2 3
output:
0 6 2 1 2 1 6 1 5 1 3 1 1
result:
ok You are right!
Test #2:
score: 0
Accepted
time: 3ms
memory: 58012kb
input:
7 7 1 2 1 3 2 3 2 4 2 5 3 6 3 7
output:
0 11 1 4 1 2 1 3 2 1 1 1 2 1 3 1 4 1 5 1 6 1 7
result:
ok You are right!
Test #3:
score: 0
Accepted
time: 83ms
memory: 72832kb
input:
300000 368742 1 143504 1 234282 2 91276 2 296320 3 274816 4 212293 4 258214 5 253489 5 295826 6 96521 6 252745 6 267103 6 269879 7 5293 7 295586 8 44304 8 57067 8 233291 9 190526 10 18682 11 7440 12 24695 12 172561 12 243692 12 280316 13 80152 13 268749 14 146394 14 207280 15 151280 15 226848 16 458...
output:
0 521843 1 3 1 274816 1 273658 1 231418 1 293414 1 210743 1 117739 1 217554 1 234392 1 48428 1 210477 1 127525 1 217572 1 248509 1 8 1 57067 1 9 1 10 1 18682 1 297029 1 148043 1 194189 1 287574 1 143622 1 247826 1 170188 1 66660 1 206230 1 26612 1 7163 1 298776 1 92709 1 69100 1 297777 1 267639 1 23...
result:
ok You are right!
Test #4:
score: 0
Accepted
time: 102ms
memory: 87948kb
input:
221155 322762 1 16446 1 214165 2 22590 2 67599 2 77971 2 173665 3 93601 3 218260 4 78445 4 126476 5 85674 5 129671 6 105765 6 161364 7 16742 7 19554 7 28037 7 51308 7 57193 7 151371 7 173612 7 218897 8 50830 8 178401 9 36068 9 198155 10 31227 10 57914 11 104822 11 196836 12 57848 12 129309 13 17006 ...
output:
0 424372 2 1 18651 1 306425 1 239806 1 85270 1 144830 1 406677 1 365985 1 185522 1 205002 1 437148 1 426157 1 215993 1 79933 1 425120 1 301088 1 203965 1 215243 1 440531 1 436398 1 219376 1 131882 1 429033 1 353037 1 207878 1 16118 1 258706 1 237273 1 37551 1 58133 1 336353 1 279288 1 115198 1 16126...
result:
ok You are right!
Test #5:
score: 0
Accepted
time: 156ms
memory: 96364kb
input:
299999 449997 1 135132 1 274953 2 18542 2 217508 3 47624 3 205183 4 121104 4 270541 5 117846 5 249889 6 272286 6 286376 7 63903 7 89777 8 153806 8 271509 9 49792 9 220343 10 4543 10 293635 11 99727 11 261001 12 29177 12 108823 13 119446 13 183797 14 210754 14 247874 15 53747 15 122774 15 179117 15 2...
output:
0 599998 2 1 247479 1 595239 1 547478 1 295240 1 103223 1 478168 1 403222 1 178169 1 30833 1 537899 1 330832 1 237900 1 202262 1 595783 1 502261 1 295784 1 287924 1 595074 1 587923 1 295075 1 83754 1 575200 1 383753 1 275201 1 81264 1 464069 1 381263 1 164070 1 79788 1 541654 1 379787 1 241655 1 105...
result:
ok You are right!
Test #6:
score: 0
Accepted
time: 105ms
memory: 80836kb
input:
300000 399999 1 215446 1 231704 2 115181 2 170051 3 1993 3 176144 4 18113 5 34133 5 53137 6 163395 6 256615 7 39049 7 128932 8 193977 8 205442 9 2810 9 260471 10 169593 10 278417 11 56849 11 139915 12 78729 12 164991 13 55416 13 62164 14 195504 14 254962 15 41739 15 143315 16 61905 16 244260 16 2772...
output:
0 511127 1 4 1 16 1 18 1 22 1 285958 1 218367 1 29 1 30 1 278005 1 256885 1 32 1 293588 1 181630 1 257757 1 174373 1 109574 1 124219 1 80024 1 233192 1 73801 1 65458 1 106097 1 64852 1 230971 1 35 1 139478 1 250704 1 231248 1 195032 1 226030 1 220272 1 259694 1 222138 1 122734 1 52731 1 175580 1 185...
result:
ok You are right!
Test #7:
score: 0
Accepted
time: 166ms
memory: 101012kb
input:
299999 449997 1 207233 1 249849 2 26483 2 120133 3 48410 3 154146 3 264694 3 276131 4 33119 4 235166 5 104107 5 256329 6 121201 6 153902 7 217994 7 249799 8 98561 8 149095 8 161763 8 244331 9 113135 9 263126 10 78235 10 93112 11 58805 11 104743 11 135998 11 140583 11 199748 11 227329 12 34054 12 124...
output:
0 599998 2 1 241472 1 565817 1 541471 1 265818 1 150985 1 593412 1 450984 1 293413 1 18267 1 484004 1 318266 1 184005 1 10372 1 574749 1 310371 1 274750 1 112297 1 532682 1 412296 1 232683 1 203489 1 584797 1 503488 1 284798 1 173078 1 525978 1 473077 1 225979 1 173528 1 477507 1 473527 1 177508 1 3...
result:
ok You are right!
Test #8:
score: 0
Accepted
time: 139ms
memory: 94612kb
input:
280291 392867 1 18749 1 136817 2 63519 2 159662 2 172896 2 251761 3 1878 3 142748 4 203284 4 228584 5 15844 5 50208 6 136817 6 245137 7 64955 7 165499 8 136817 8 220201 9 136817 9 191205 10 136817 10 192877 11 139542 11 162473 12 57326 12 190877 13 33859 13 153427 14 110791 14 136817 15 16389 15 864...
output:
0 505446 2 1 104115 1 560582 1 384406 1 280291 1 51999 1 560581 1 332290 1 280290 1 126720 1 560579 1 407011 1 280288 1 166945 1 560577 1 447236 1 280286 1 197162 1 560575 1 477453 1 280284 1 97348 1 560571 1 377639 1 280280 1 175910 1 560565 1 456201 1 280274 1 1913 1 560561 1 282204 1 280270 1 654...
result:
ok You are right!
Test #9:
score: 0
Accepted
time: 137ms
memory: 99572kb
input:
292995 410094 1 71999 1 169963 2 98256 2 132856 3 132856 3 165225 4 82003 4 132856 5 132364 5 160935 6 35335 6 147436 7 132856 7 255985 8 132856 8 200164 9 4463 9 156552 10 2320 10 99646 11 132856 11 185279 12 110686 12 285870 13 73136 13 275400 14 121746 14 132856 15 153856 15 278178 16 83552 16 21...
output:
0 527196 2 1 77459 1 511876 1 370454 1 218881 1 26086 1 461006 1 319081 1 168011 1 108529 1 585780 1 401524 1 292785 1 9828 1 455615 1 302823 1 162620 1 62270 1 359017 1 355265 1 66022 1 79913 1 384082 1 372908 1 91087 1 175900 1 564115 1 468895 1 271120 1 35977 1 405337 1 328972 1 112342 1 64656 1 ...
result:
ok You are right!
Test #10:
score: 0
Accepted
time: 70ms
memory: 75028kb
input:
300000 403707 1 129294 1 278573 2 11106 2 129294 3 184237 3 221196 4 55817 4 100929 4 136405 4 238314 5 31450 5 186997 6 4795 7 129294 7 163574 8 61455 8 129294 9 21984 9 129294 10 231237 11 129294 11 228549 12 129294 12 224390 13 19505 13 26574 14 55849 14 98378 15 23106 16 4025 16 100577 17 67090 ...
output:
0 495447 1 6 1 10 1 231237 1 202835 1 211771 1 246477 1 179590 1 136958 1 85805 1 277287 1 109635 1 194541 1 15 1 23106 1 19 1 20 1 110694 1 68436 1 14262 1 110432 1 247212 1 252571 1 244837 1 11639 1 171293 1 141945 1 25 1 26 1 37 1 90299 1 43 1 44 1 220797 1 294298 1 210713 1 53091 1 221361 1 1483...
result:
ok You are right!
Test #11:
score: 0
Accepted
time: 8ms
memory: 55176kb
input:
1 0
output:
0 2 2 1 1
result:
ok You are right!
Test #12:
score: 0
Accepted
time: 66ms
memory: 74152kb
input:
255596 313062 1 10655 1 15889 1 35851 1 220010 1 243820 2 236476 3 75462 3 240876 3 241881 4 164691 5 112681 6 31313 6 40322 6 89447 6 199617 7 78108 7 249785 8 180866 8 225929 9 26444 10 209074 11 108986 12 147579 12 165165 13 53313 13 182814 13 230088 14 124147 15 73182 15 98755 15 212191 16 98391...
output:
0 415862 1 1 1 243820 1 15889 1 220010 1 10655 1 216583 1 153398 1 68743 1 101829 1 2 1 3 1 241881 1 1722 1 240876 1 75462 1 4 1 5 1 9 1 10 1 209074 1 198280 1 11 1 108986 1 13 1 230088 1 172214 1 34773 1 14 1 124147 1 5520 1 116944 1 9028 1 187645 1 118571 1 44283 1 241641 1 54572 1 208686 1 152031...
result:
ok You are right!
Test #13:
score: 0
Accepted
time: 111ms
memory: 90964kb
input:
244001 330353 1 33864 1 90721 1 120604 1 122898 1 195228 1 211057 2 9529 2 118870 3 35564 3 229469 4 81097 4 236945 5 47476 5 223470 6 46769 6 48597 7 49304 7 146411 7 154996 7 220507 8 14839 8 162760 9 85423 9 114698 10 4239 10 32108 10 39949 10 85700 11 160326 11 205183 12 25068 12 156392 13 13985...
output:
0 416708 2 1 190073 1 484457 1 434074 1 240456 1 184800 1 453494 1 428801 1 209493 1 60200 1 367466 1 304201 1 123465 1 174007 1 454395 1 418008 1 210394 1 24717 1 396289 1 268718 1 152288 1 157322 1 428638 1 401323 1 184637 1 114245 1 485710 1 358246 1 241709 1 44153 1 324218 1 288154 1 80217 1 377...
result:
ok You are right!