oj.uz

Submission #258766

# Submission time Handle Problem Language Result Execution time Memory
258766 2020-08-06T14:22:53 Z davooddkareshki Synchronization (JOI13_synchronization) C++17
100 / 100
 730 ms 38992 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 5 ms 5120 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 5 ms 5120 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 27 ms 7936 KB Output is correct
8 Correct 25 ms 7936 KB Output is correct
9 Correct 26 ms 7936 KB Output is correct
10 Correct 373 ms 33784 KB Output is correct
11 Correct 370 ms 33784 KB Output is correct
12 Correct 420 ms 38008 KB Output is correct
13 Correct 228 ms 32868 KB Output is correct
14 Correct 257 ms 32412 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 34800 KB Output is correct
2 Correct 214 ms 34288 KB Output is correct
3 Correct 223 ms 36724 KB Output is correct
4 Correct 226 ms 36716 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 60 ms 8448 KB Output is correct
8 Correct 730 ms 38992 KB Output is correct
9 Correct 725 ms 38932 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 38776 KB Output is correct
2 Correct 522 ms 37624 KB Output is correct
3 Correct 533 ms 37880 KB Output is correct
4 Correct 523 ms 37880 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB Output is correct
2 Correct 5 ms 5120 KB Output is correct
3 Correct 3 ms 5120 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 8 ms 5376 KB Output is correct
6 Correct 53 ms 7936 KB Output is correct
7 Correct 645 ms 34808 KB Output is correct
8 Correct 720 ms 38896 KB Output is correct
9 Correct 493 ms 34148 KB Output is correct
10 Correct 497 ms 33784 KB Output is correct
11 Correct 473 ms 36120 KB Output is correct
12 Correct 489 ms 35952 KB Output is correct
13 Correct 559 ms 37880 KB Output is correct