oj.uz

Submission #954039

# Submission time Handle Problem Language Result Execution time Memory
954039 2024-03-27T06:44:39 Z Trisanu_Das Synchronization (JOI13_synchronization) C++17
100 / 100
 91 ms 16992 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]
   10 |  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'
   10 |  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]
   11 |  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'
   11 |  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]
   22 |  scanf("%i %i %i",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:23:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  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]
   27 |   scanf("%i",&d);
      |   ~~~~~^~~~~~~~~
synchronization.cpp:44:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  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 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 7 ms 5228 KB Output is correct
8 Correct 6 ms 5208 KB Output is correct
9 Correct 6 ms 5212 KB Output is correct
10 Correct 67 ms 11604 KB Output is correct
11 Correct 58 ms 11600 KB Output is correct
12 Correct 54 ms 16212 KB Output is correct
13 Correct 44 ms 10956 KB Output is correct
14 Correct 49 ms 11100 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 13708 KB Output is correct
2 Correct 44 ms 13476 KB Output is correct
3 Correct 38 ms 15700 KB Output is correct
4 Correct 38 ms 15812 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 8 ms 5724 KB Output is correct
8 Correct 74 ms 16980 KB Output is correct
9 Correct 82 ms 16976 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 16976 KB Output is correct
2 Correct 61 ms 16908 KB Output is correct
3 Correct 62 ms 16976 KB Output is correct
4 Correct 63 ms 16992 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 8 ms 5468 KB Output is correct
7 Correct 80 ms 12704 KB Output is correct
8 Correct 73 ms 16976 KB Output is correct
9 Correct 64 ms 12740 KB Output is correct
10 Correct 91 ms 12476 KB Output is correct
11 Correct 66 ms 14928 KB Output is correct
12 Correct 69 ms 15012 KB Output is correct
13 Correct 61 ms 16980 KB Output is correct