Submission #154847

#	Time	Username	Problem	Language	Result	Execution time	Memory
154847		TadijaSebez	Pipes (CEOI15_pipes)	C++11	40 / 100	5079 ms	28312 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
const int N=200050;
int fa[N],go[N][2];
short tag[N];
void push(int x)
{
	if(tag[x]&1)
	{
		swap(go[x][0],go[x][1]);
		if(go[x][0]) tag[go[x][0]]^=1;
		if(go[x][1]) tag[go[x][1]]^=1;
		tag[x]--;
	}
	if(tag[x]&2)
	{
		tag[x]|=4;
		if(go[x][0]) tag[go[x][0]]|=2;
		if(go[x][1]) tag[go[x][1]]|=2;
		tag[x]-=2;
	}
}
int pd(int x){ return go[fa[x]][0]==x?0:go[fa[x]][1]==x?1:-1;}
void rot(int x)
{
	int y=fa[x],z=fa[y],p=pd(x),q=pd(y),w=go[x][p^1];
	if(~q) go[z][q]=x;go[y][p]=w;go[x][p^1]=y;
	if(w) fa[w]=y;fa[y]=x;fa[x]=z;
}
int stk[N],top;
void cl(int x){ do stk[++top]=x;while(~pd(x) && !((x=fa[x])*0));for(;top;push(stk[top--]));}
void splay(int x){ for(cl(x);~pd(x);rot(x)) if(~pd(fa[x])) rot(pd(fa[x])==pd(x)?fa[x]:x);}
void access(int x){ for(splay(x),go[x][1]=0;fa[x];rot(x)) splay(fa[x]),go[fa[x]][1]=x;}
void make_rt(int x){ access(x);tag[x]^=1;push(x);}
void link(int x, int y){ make_rt(x);fa[x]=y;}
int get_rt(int x){ access(x);for(push(x);go[x][0];push(x)) x=go[x][0];splay(x);return x;}
int U[N/2],V[N/2];
int main()
{
	int n,m;
	scanf("%i %i",&n,&m);
	int tmp=n;
	for(int i=1,u,v;i<=m;i++)
	{
		scanf("%i %i",&u,&v);
		make_rt(u);
		int rt=get_rt(v);
		if(rt!=u)
		{
			n++;
			U[n-tmp]=u;V[n-tmp]=v;
			link(u,n);
			link(v,n);
		}
		else
		{
			access(v);
			tag[v]|=2;
			push(v);
		}
	}
	for(int i=tmp+1;i<=n;i++)
	{
		splay(i);
		if((tag[i]&4)==0) printf("%i %i\n",U[i-tmp],V[i-tmp]);
	}
	return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'void rot(int)':
pipes.cpp:27:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(~q) go[z][q]=x;go[y][p]=w;go[x][p^1]=y;
  ^~
pipes.cpp:27:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(~q) go[z][q]=x;go[y][p]=w;go[x][p^1]=y;
                    ^~
pipes.cpp:28:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(w) fa[w]=y;fa[y]=x;fa[x]=z;
  ^~
pipes.cpp:28:16: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(w) fa[w]=y;fa[y]=x;fa[x]=z;
                ^~
pipes.cpp: In function 'void cl(int)':
pipes.cpp:31:60: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
 void cl(int x){ do stk[++top]=x;while(~pd(x) && !((x=fa[x])*0));for(;top;push(stk[top--]));}
                                                  ~~~~~~~~~~^~~
pipes.cpp: In function 'int main()':
pipes.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
pipes.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&u,&v);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 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