Submission #1178802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178802		sleepntsheep	Pipes (CEOI15_pipes)	C++20	0 / 100	87 ms	131072 KiB

pipes

#include<stdio.h>
#include<algorithm>
#define N 200005

int n,m,ds[N],rk[N],trash[100002],top,ii,ded[N];

int fin(int i){
    return ds[i]==i?i:(ds[i]=fin(ds[i]));
}
void unite(int i,int j){
    i=fin(i),j=fin(j);
    if(i==j)return;
    if(rk[i]==rk[j]){
	ds[j]=i;
	++rk[i];
    }
    else{
	if(rk[i]<rk[j]) std::swap(i,j);
	ds[j]=i;
    }
}

struct LCT{
    struct node{int c[2],pa,rev,eu,ev;}t[200005];
    int nrt(int v){return t[t[v].pa].c[0]==v||t[t[v].pa].c[1]==v;}
    int newnode(){
	int i=top?trash[--top]:++ii;
	ds[i]=i;rk[i]=0;
	t[i].c[0]=t[i].c[1]=t[i].pa=t[i].rev=0;
	return i;
    }
    void tagrev(int v){
	if(v){
	    std::swap(t[v].c[0],t[v].c[1]);
	    t[v].rev^=1;
	}
    }
    void pushdown(int v){
	if(t[v].rev){
	    tagrev(t[v].c[0]),tagrev(t[v].c[1]);
	    t[v].rev=0;
	}
    }
    void rot(int v){
	int p=t[v].pa,g=t[p].pa,d=t[p].c[1]==v;
	if(nrt(p))t[g].c[t[g].c[1]==p]=v;
	t[p].c[d]=t[v].c[!d];
	if(t[v].c[!d])t[t[v].c[!d]].pa=p;
	t[v].c[!d]=p;
	t[t[p].pa=v].pa=g;
    }
    void upd(int v){if(nrt(v))upd(t[v].pa);pushdown(v);}
    void splay(int v){
	upd(v);
	for(int p,g;nrt(v);rot(v)){
	    g=t[p=t[v].pa].pa;
	    if(nrt(p))rot((t[p].c[1]==v)==(t[g].c[1]==p)?p:v);
	}
    }
    void access(int v){
	for(int w=0;v;w=v,v=t[v].pa=fin(t[v].pa))
	    splay(v),
		t[v].c[1]=w;
    }
    void evert(int v){
	access(v);splay(v);tagrev(v);
    }
    int frt(int v){
	access(v);splay(v);
	while(t[v].c[0])v=t[v].c[0];
	splay(v);return v;
    }
    void link(int v,int w){
	evert(v);access(w);splay(w);t[v].pa=w;
    }
    void dfs(int v,int rt){
	if(!v)return;
	if(v<=n)
	    unite(rt,v);
	else{
	    ded[v]=1,trash[top++]=v;
	}
	dfs(t[v].c[0],rt);
	dfs(t[v].c[1],rt);
	t[v].c[0]=t[v].c[1]=0;
    }
}lc;

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<N;++i)ds[i]=i;
    ii=n;
    for(int u,v,i=0;i<m;++i){
	scanf("%d%d",&u,&v);
	if(fin(u)==fin(v))continue;
	if(lc.frt(u)==lc.frt(v)){
	    lc.evert(u);
	    lc.access(v);
	    lc.splay(v);
	    lc.dfs(v,v);
	}else{
	    int j=lc.newnode();
	    lc.t[j].eu=u,lc.t[j].ev=v;
	    ded[j]=0;
	    lc.link(u,j);
	    lc.link(j,v);
	}
    }
    for(int i=n+1;i<=ii;++i){
	if(!ded[i]){
	    printf("%d %d\n",lc.t[i].eu,lc.t[i].ev);
	}
    }

    return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
pipes.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10