QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#327844 | #1844. Cactus | yqh2025 | ML | 8ms | 28840kb | C++14 | 1.6kb | 2024-02-15 15:00:02 | 2024-02-15 15:00:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,m;
vector<int>E[N<<1],G[N],ans;
int deg[N],dfn[N],low[N],tot,top,st[N],dl[N],cnt;
void an(int x){ans.push_back(x);}
void del(int x){
an(x);
dl[x]=1;deg[x]=0;
for(int v:E[x])if(!dl[v])deg[v]^=1;
for(int v:E[x])if(deg[v])del(v);
}
void dfs(int u){
dfn[u]=low[u]=++tot;st[++top]=u;
for(int v:G[u]){
if(!dfn[v]){
dfs(v);
if(low[v]>=dfn[u]){
cnt++;
while(st[top]!=v){
E[cnt].push_back(st[top]);
E[st[top]].push_back(cnt);
top--;
}
E[cnt].push_back(v);
E[v].push_back(cnt);
E[cnt].push_back(u);
E[u].push_back(cnt);
}
else low[u]=min(low[u],low[v]);
}
else low[u]=min(low[u],dfn[v]);
}
}
int vis[N],a[N];
void sol(int u,int fa){
vis[u]=1;
for(int v:E[u])if(v!=fa)sol(v,u);
if(u<=n){
if(!fa)an(u);
return;
}
int p=0,m=E[u].size();
for(int i=0;i<m;i++)if(E[u][i]==fa)p=i;
for(int i=0;i<m;i++)a[i]=E[u][(p+i)%m];
for(int i=1;i<m;i++)an(a[i]+((i&1)^1)*n);
an(a[m-1]+((m-1)&1)*n);an(a[1]+n);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
E[x].push_back(y);E[y].push_back(x);
deg[x]^=1;deg[y]^=1;
}
for(int i=1;i<=n;i++)if(deg[i]&1)del(i);
an(0);
for(int i=1;i<=n;i++){
if(!dl[i]){
for(int j:E[i]){
if(!dl[j])G[i].push_back(j),G[j].push_back(i);
}
}
}
for(int i=1;i<=n;i++)E[i].clear();
cnt=n;
for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
for(int i=1;i<=n;i++)if(!vis[i])sol(i,0);
printf("0 %d\n",ans.size());
for(int i:ans){
if(i==0)printf("2\n");
else printf("1 %d\n",i);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 26828kb
input:
3 3 1 2 1 3 2 3
output:
0 6 2 1 3 1 5 1 2 1 6 1 1
result:
ok You are right!
Test #2:
score: 0
Accepted
time: 8ms
memory: 28840kb
input:
7 7 1 2 1 3 2 3 2 4 2 5 3 6 3 7
output:
0 13 1 4 1 2 1 1 1 6 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: -100
Memory Limit Exceeded
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...