oj.uz

Submission #154847

# Submission time Handle Problem Language Result Execution time Memory
154847 2019-09-25T10:25:10 Z TadijaSebez Pipes (CEOI15_pipes) C++11
40 / 100
 5000 ms 28312 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 632 KB Output is correct
2 Correct 14 ms 632 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 5884 KB Output is correct
2 Correct 703 ms 5880 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1654 ms 10300 KB Output is correct
2 Correct 1696 ms 12024 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2848 ms 17352 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4200 ms 23420 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5078 ms 27752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5005 ms 27388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5030 ms 27516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5079 ms 28312 KB Time limit exceeded
2 Halted 0 ms 0 KB -