oj.uz

Submission #151967

# Submission time Handle Problem Language Result Execution time Memory
151967 2019-09-05T17:07:11 Z TadijaSebez Synchronization (JOI13_synchronization) C++11
100 / 100
 183 ms 17144 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(q!=-1) 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;}
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);fa[a]=0;
		}
		else
		{
			int r=rt(b);
			ans[r]+=ans[a]-last[a];
			splay(a);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(q!=-1) go[z][q]=x;go[x][p^1]=y;go[y][p]=w;
  ^~
synchronization.cpp:10:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(q!=-1) 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:22: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:23: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:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&d);
   ~~~~~^~~~~~~~~
synchronization.cpp:44: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
10.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 Correct 4 ms 2680 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 13 ms 3576 KB Output is correct
8 Correct 15 ms 3576 KB Output is correct
9 Correct 13 ms 3576 KB Output is correct
10 Correct 172 ms 11768 KB Output is correct
11 Correct 160 ms 11768 KB Output is correct
12 Correct 99 ms 16332 KB Output is correct
13 Correct 77 ms 10864 KB Output is correct
14 Correct 106 ms 10804 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 11768 KB Output is correct
2 Correct 78 ms 13176 KB Output is correct
3 Correct 68 ms 15400 KB Output is correct
4 Correct 68 ms 15608 KB Output is correct

Subtask #3
10.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 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2680 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 15 ms 4088 KB Output is correct
8 Correct 133 ms 17072 KB Output is correct
9 Correct 126 ms 17112 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 15456 KB Output is correct
2 Correct 103 ms 16448 KB Output is correct
3 Correct 102 ms 16568 KB Output is correct
4 Correct 102 ms 16632 KB Output is correct

Subtask #5
40.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 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 17 ms 3624 KB Output is correct
7 Correct 156 ms 12536 KB Output is correct
8 Correct 128 ms 17144 KB Output is correct
9 Correct 103 ms 12684 KB Output is correct
10 Correct 183 ms 12124 KB Output is correct
11 Correct 106 ms 14712 KB Output is correct
12 Correct 105 ms 14712 KB Output is correct
13 Correct 106 ms 16596 KB Output is correct