Submission #954039

#	Time	Username	Problem	Language	Result	Execution time	Memory
954039		Trisanu_Das	Synchronization (JOI13_synchronization)	C++17	100 / 100	91 ms	16992 KiB

synchronization

#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 (stderr)

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