oj.uz

Submission #545176

# Submission time Handle Problem Language Result Execution time Memory
545176 2022-04-03T20:27:58 Z MilosMilutinovic Synchronization (JOI13_synchronization) C++14
100 / 100
 293 ms 25008 KB 
#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<typename T> bool chkmin(T&x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T&x,T y){return x<y?x=y,1:0;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,m,q,x[200005],y[200005],ans[100005],dep[100005],dfn[100005],dfo[100005],T,fnw[200005],f[100005][20],snc[100005];
vector<int> adj[100005];
bool act[200005];

void dfs(int u,int p){
	dfn[u]=++T,ans[u]=1,dep[u]=dep[p]+1,f[u][0]=p;
	for(int i=1;i<20;i++) f[u][i]=f[f[u][i-1]][i-1];
	for(int v:adj[u]) if(v!=p) dfs(v,u);
	dfo[u]=++T;
}

void modify(int x,int v){
	for(;x<200005;x+=x&-x) fnw[x]+=v;
}
int query(int x){
	int s=0;
	for(;x>0;x-=x&-x) s+=fnw[x];
	return s;
}

int getf(int x){
	int r=x;
	for(int i=19;i>=0;i--) if(f[r][i]&&query(dfn[f[r][i]])==query(dfn[x])) r=f[r][i];
	return r;
}

int main(){
	n=readint(); m=readint(); q=readint();
	for(int i=1;i<n;i++){
		x[i]=readint(); y[i]=readint();
		adj[x[i]].pb(y[i]);
		adj[y[i]].pb(x[i]);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++) modify(dfn[i],1),modify(dfo[i],-1);
	while(m--){
		int i=readint();
		if(dep[x[i]]>dep[y[i]])swap(x[i],y[i]);
		if(act[i]){
			ans[y[i]]=snc[y[i]]=ans[getf(x[i])];
			modify(dfn[y[i]],1); modify(dfo[y[i]],-1);
		}else{
			ans[getf(x[i])]+=ans[y[i]]-snc[y[i]];
			modify(dfn[y[i]],-1); modify(dfo[y[i]],1);
		}
		act[i]=!act[i];
	}
	while(q--)printf("%d\n",ans[getf(readint())]);
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2812 KB Output is correct
7 Correct 11 ms 4328 KB Output is correct
8 Correct 10 ms 4308 KB Output is correct
9 Correct 12 ms 4340 KB Output is correct
10 Correct 195 ms 19624 KB Output is correct
11 Correct 155 ms 19540 KB Output is correct
12 Correct 213 ms 24204 KB Output is correct
13 Correct 65 ms 19520 KB Output is correct
14 Correct 128 ms 18620 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 19444 KB Output is correct
2 Correct 64 ms 19276 KB Output is correct
3 Correct 94 ms 21476 KB Output is correct
4 Correct 89 ms 21544 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2900 KB Output is correct
7 Correct 17 ms 4640 KB Output is correct
8 Correct 282 ms 22040 KB Output is correct
9 Correct 247 ms 22092 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 22076 KB Output is correct
2 Correct 149 ms 21968 KB Output is correct
3 Correct 147 ms 22108 KB Output is correct
4 Correct 171 ms 22184 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2808 KB Output is correct
6 Correct 14 ms 4420 KB Output is correct
7 Correct 205 ms 20552 KB Output is correct
8 Correct 271 ms 25008 KB Output is correct
9 Correct 75 ms 20584 KB Output is correct
10 Correct 169 ms 19908 KB Output is correct
11 Correct 99 ms 22604 KB Output is correct
12 Correct 86 ms 22632 KB Output is correct
13 Correct 135 ms 24416 KB Output is correct