Submission #258766

#	Time	Username	Problem	Language	Result	Execution time	Memory
258766		davooddkareshki	Synchronization (JOI13_synchronization)	C++17	100 / 100	730 ms	38992 KiB

synchronization

#include<bits/stdc++.h>

using namespace std;
 
#define int long long
#define F first 
#define S second 
#define pii pair<int,int> 
#define mpr make_pair

typedef long long ll;

const int maxn = 2e5+10;
const int mod = 1e9+7;
const ll inf = 1e18+10;

int n, q, k;

int fen[maxn];
void _add(int pos, int val) {for(; pos <= n; pos |= (pos+1)) fen[pos] += val;}
void fen_add(int l, int r, int val) {_add(l,val); _add(r+1,-val);}
int fen_qu(int pos) {int res = 0; for(; pos >= 0; pos = (pos&(pos+1))-1) res += fen[pos]; return res;}

vector<pii> g[maxn]; 
int st[maxn], tin[maxn], tim, h[maxn];
int par[maxn][20], id[maxn];

void add(int v, int val) {fen_add(tin[v], tin[v]+st[v]-1, val);}
int qu(int v) {return fen_qu(tin[v]);}


void dfs(int v)
{
	for(int i = 1; (1<<i) <= h[v]; i++)
		par[v][i] = par[par[v][i-1]][i-1];
	
	st[v] = 1;
	tin[v] = ++tim;
	for(auto e : g[v])
	{
		int u = e.F; 
		if(u != par[v][0])
		{	
			id[e.S] = u;
			par[u][0] = v;
			h[u] = h[v] + 1;
			dfs(u);
			st[v] += st[u];
		}	
	}
}

int get_par(int v)
{
	for(int i = 19; i >= 0; i--)
		if(par[v][i] && ((qu(v) - qu(par[v][i])) == (1<<i))) 
			v = par[v][i];
	return v;
}
bool is[maxn];
int ans[maxn], last_ans[maxn];

signed main()
{
	//ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);	
	
	cin>> n >> q >> k;
	for(int i = 1, u, v; i < n; i++)
	{
		cin>> u >> v;
		g[u].push_back({v,i});
		g[v].push_back({u,i});
	}
	dfs(1); for(int i = 1; i <= n; i++) ans[i] = 1;
	
	while(q--)
	{
		int e; cin>> e;
		int v = id[e]; int u = par[v][0];	
		int lca = get_par(u);	
	//	cout<< u <<" "<< lca <<"\n";	
	
		if(is[e])
		{
			last_ans[v] = ans[lca];
			ans[v] = ans[lca];
			add(v,-1);	
		}
		else 
		{	
			ans[lca] += ans[v] - last_ans[v];
			add(v,1);
		}
		(is[e] ^= 1);	
	}

	while(k--)
	{
		int v; cin>> v;
		cout<< ans[get_par(v)] <<"\n";
	}	
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40