oj.uz

Submission #871778

# Submission time Handle Problem Language Result Execution time Memory
871778 2023-11-11T14:30:26 Z sunwukong123 Synchronization (JOI13_synchronization) C++14
100 / 100
 228 ms 57168 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = 200005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
/*
you need a "dynamic UFDS" on tree which supports connection and deletion between parent and child nodes
when disconnecting, carry the ans from the current ufds group's root to this ufds group's root. 
when connecting, add the ans for the child's ufds group to the parent's ufds group. (keep track of how many more nodes there are now)
*/
int twok[MAXN][19];
int st[MAXN], en[MAXN];
int TIME=1;
vector<int> adj[MAXN];
int n,m,q;
int ans[MAXN], lst[MAXN], state[MAXN];
namespace fw {
	int fw[MAXN];
	void update(int x, int nval){
		for(;x<MAXN;x+=x&-x)fw[x]+=nval;
	}
	void update(int x,int y, int nval){
		update(x,nval);
		update(y+1,-nval);
	}
	int query(int x){
		int res=0;
		for(;x;x-=x&-x)res+=fw[x];
		return res;
	}
};
int find(int x){ // finds the parent
	for(int i=18;i>=0;i--){
		if(twok[x][i]==-1)continue;
		if(fw::query(st[x]) == fw::query(st[twok[x][i]])){
			x=twok[x][i];
		}
	}
	return x;
}
void dfs(int x, int p){
	st[x]=TIME++;
	twok[x][0]=p;
	for(int i=1;i<=18;i++){
		if(twok[x][i-1] == -1)continue;

		twok[x][i]=twok[twok[x][i-1]][i-1];
	}
	for(auto v:adj[x])if(v!=p){
		dfs(v,x);
	}
	

	en[x]=TIME-1;
}
pi E[MAXN];
int32_t main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	memset(twok,-1,sizeof twok);
	cin >> n >> m >> q;
	for(int i=1;i<=n-1;i++){
		int a,b; cin >> a >> b;
		E[i].first=a;
		E[i].second=b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for(int i=1;i<=n;i++)ans[i]=1;

	dfs(1,-1);
	for(int i=1;i<=n;i++){
		fw::update(st[i],en[i],1);//there is blockage between child and parent.
	}

	for(int t=1;t<=m;t++){

		int edge; cin >> edge;
		int par=E[edge].first;
		int child=E[edge].second;
		if(st[par]>st[child])swap(par,child);

		if(!state[edge]){ // activate
			int rt=find(par);
			ans[rt] += ans[child] - lst[child];
			fw::update(st[child],en[child],-1);
		} else{
			int rt=find(par);
			ans[child]=lst[child]=ans[rt];
			fw::update(st[child],en[child],1);
		}
		state[edge] = !state[edge];
	}
	while(q--){
		int x; cin >> x;
		cout<<ans[find(x)]<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 43100 KB Output is correct
2 Correct 6 ms 43100 KB Output is correct
3 Correct 6 ms 43096 KB Output is correct
4 Correct 6 ms 43020 KB Output is correct
5 Correct 6 ms 43096 KB Output is correct
6 Correct 7 ms 43100 KB Output is correct
7 Correct 14 ms 43784 KB Output is correct
8 Correct 14 ms 43868 KB Output is correct
9 Correct 14 ms 44036 KB Output is correct
10 Correct 137 ms 52496 KB Output is correct
11 Correct 140 ms 52044 KB Output is correct
12 Correct 185 ms 56144 KB Output is correct
13 Correct 53 ms 51908 KB Output is correct
14 Correct 97 ms 51776 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 51920 KB Output is correct
2 Correct 72 ms 53744 KB Output is correct
3 Correct 94 ms 55632 KB Output is correct
4 Correct 91 ms 55636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 43100 KB Output is correct
2 Correct 6 ms 43100 KB Output is correct
3 Correct 6 ms 43144 KB Output is correct
4 Correct 6 ms 43100 KB Output is correct
5 Correct 6 ms 42988 KB Output is correct
6 Correct 7 ms 43100 KB Output is correct
7 Correct 19 ms 44380 KB Output is correct
8 Correct 215 ms 57168 KB Output is correct
9 Correct 228 ms 56980 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 54128 KB Output is correct
2 Correct 135 ms 56660 KB Output is correct
3 Correct 133 ms 56828 KB Output is correct
4 Correct 133 ms 56692 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 43100 KB Output is correct
2 Correct 6 ms 43100 KB Output is correct
3 Correct 6 ms 43024 KB Output is correct
4 Correct 6 ms 42944 KB Output is correct
5 Correct 7 ms 43220 KB Output is correct
6 Correct 17 ms 43868 KB Output is correct
7 Correct 154 ms 52896 KB Output is correct
8 Correct 219 ms 56976 KB Output is correct
9 Correct 73 ms 53188 KB Output is correct
10 Correct 117 ms 52796 KB Output is correct
11 Correct 92 ms 55048 KB Output is correct
12 Correct 92 ms 55244 KB Output is correct
13 Correct 133 ms 56692 KB Output is correct