Submission #1178815

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

pipes

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

int MS;
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;
    //printf(" Unite %d %d\n",i,j);
    ds[j]=i;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;ded[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 cut(int v){
	access(v);
	splay(v);
	t[t[v].c[0]].pa=0;
	t[v].c[0]=0;
    }
    std::vector<int>b;
    void bfs(int v){
	std::queue<int>q;
	q.push(v);
	while(q.size()){
	    int v=q.front();q.pop();
	    b.push_back(v);
	    if(t[v].c[0])q.push(t[v].c[0]);
	    if(t[v].c[1])q.push(t[v].c[1]);
	}
    }
}lc;

int ME;
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);
	int u0=u,v0=v;
	if(fin(u)==fin(v))continue;
	u=fin(u),v=fin(v);
	if(lc.frt(u)==lc.frt(v)){
	    lc.evert(u);
	    lc.access(v);
	    lc.splay(v);
	    lc.b.clear();
	    lc.bfs(v);
	    for(auto x:lc.b){
		if(x>n){
		    lc.evert(x);
		    lc.cut(lc.t[x].eu);
		    lc.cut(lc.t[x].ev);
		    trash[top++]=x;
		    ded[x]=1;
		}
	    }
	    for(auto x:lc.b){
		if(x<=n)
		    unite(v,x);
		lc.t[x].c[0]=lc.t[x].c[1]=0;
	    }
	}else{
	    int j=lc.newnode();
	    lc.t[j].eu=u0,lc.t[j].ev=v0;
	    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:102:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
pipes.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         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