oj.uz

Submission #151963

# Submission time Handle Problem Language Result Execution time Memory
151963 2019-09-05T17:02:31 Z TadijaSebez Synchronization (JOI13_synchronization) C++11
0 / 100
 8000 ms 28228 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
int go[N][2],fa[N];
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(z) go[z][q]=x;go[x][p^1]=y;go[y][p]=w;
	if(w) fa[w]=y;fa[x]=z;fa[y]=x;
}
void splay(int x){ while(pd(x)!=-1){ if(pd(fa[x])!=-1) rot(pd(fa[x])==pd(x)?fa[x]:x);rot(x);}}
void access(int x){ for(splay(x),go[x][1]=0;fa[x];rot(x)) splay(fa[x]),go[fa[x]][1]=x;}
int rt(int x){ access(x);while(go[x][0]) x=go[x][0];splay(x);return x;}
const int M=2*N;
int ans[N],last[N],u[N],v[N],dep[N],st[N];
vector<int> E[N];
void DFS(int u, int p){ ans[u]=1;dep[u]=dep[p]+1;for(int v:E[u]) if(v!=p) DFS(v,u);}
int main()
{
	int n,m,q;
	scanf("%i %i %i",&n,&m,&q);
	for(int i=1;i<n;i++) scanf("%i %i",&u[i],&v[i]),E[u[i]].pb(v[i]),E[v[i]].pb(u[i]);
	DFS(1,0);
	for(int i=1,d;i<=m;i++)
	{
		scanf("%i",&d);
		int a=u[d],b=v[d];
		if(dep[a]<dep[b]) swap(a,b);
		if(st[d])
		{
			int r=rt(b);
			last[a]=ans[a]=ans[r];
			splay(a);
			assert(fa[a]==b);
			fa[a]=0;
		}
		else
		{
			int r=rt(b);
			ans[r]+=ans[a]-last[a];
			splay(a);
			assert(fa[a]==0);
			fa[a]=b;
		}
		st[d]^=1;
	}
	for(int x;q--;) scanf("%i",&x),printf("%i\n",ans[rt(x)]);
	return 0;
}

Compilation message

synchronization.cpp: In function 'void rot(int)':
synchronization.cpp:10:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(z) go[z][q]=x;go[x][p^1]=y;go[y][p]=w;
  ^~
synchronization.cpp:10:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(z) go[z][q]=x;go[x][p^1]=y;go[y][p]=w;
                   ^~
synchronization.cpp:11:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(w) fa[w]=y;fa[x]=z;fa[y]=x;
  ^~
synchronization.cpp:11:16: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(w) fa[w]=y;fa[x]=z;fa[y]=x;
                ^~
synchronization.cpp: In function 'int main()':
synchronization.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&m,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:24:66: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<n;i++) scanf("%i %i",&u[i],&v[i]),E[u[i]].pb(v[i]),E[v[i]].pb(u[i]);
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&d);
   ~~~~~^~~~~~~~~
synchronization.cpp:49:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int x;q--;) scanf("%i",&x),printf("%i\n",ans[rt(x)]);
                  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2684 KB Output is correct
5 Incorrect 4 ms 2680 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2684 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Execution timed out 8029 ms 2680 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 78 ms 28228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Runtime error 8 ms 5368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -