Submission #359248

#	Time	Username	Problem	Language	Result	Execution time	Memory
359248		pure_mem	Synchronization (JOI13_synchronization)	C++14	100 / 100	684 ms	23660 KiB

synchronization

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e5 + 12;

int n, m, q, tin[N], tout[N], timer, f[2 * N], lca[17][N];
int ans[N], last[N], dsu[N];
bool on[N];
pair<int, int> road[N];
vector<int> g[N];

int get(int v){
	int val = 0;
	for(;v >= 0;v = (v & (v + 1)) - 1)
		val += f[v];
	return val;
}

void upd(int v, int val){
	for(;v <= timer;v = v | (v + 1))
		f[v] += val;
}

void dfs(int v, int pr){
	lca[0][v] = pr, tin[v] = ++timer;
	for(int to: g[v]){
		if(to != pr)
			dfs(to, v);
	}
	tout[v] = ++timer;
}

int get_pr(int v){
	int kv = get(tin[v]);
	for(int i = 16;i >= 0;i--){
		if(kv == get(tin[lca[i][v]]))
			v = lca[i][v];
	}
	return v;
}

int main () {		
	scanf("%d %d %d", &n, &m, &q);
	for(int i = 1, x, y;i < n;i++){
		scanf("%d %d", &x, &y), road[i] = MP(x, y);
		g[x].push_back(y), g[y].push_back(x);
	}
	dfs(1, 1);
	for(int i = 1;i <= n;i++)
		ans[i] = 1, upd(tin[i], 1), upd(tout[i], -1);
	for(int i = 1;i <= 16;i++)
		for(int j = 1;j <= n;j++)
			lca[i][j] = lca[i - 1][lca[i - 1][j]];
	for(int v;m--;){
		scanf("%d", &v);	
		on[v] ^= 1;
		if(on[v]){
			int u = get_pr(lca[0][road[v].X] == road[v].Y ? road[v].Y: road[v].X);
			v = (lca[0][road[v].X] == road[v].Y ? road[v].X: road[v].Y);
			ans[u] = ans[u] + ans[v] - last[v];
			upd(tin[v], -1);
			upd(tout[v], 1);	
		}
		else{
			int u = get_pr(lca[0][road[v].X] == road[v].Y ? road[v].Y: road[v].X);
			v = (lca[0][road[v].X] == road[v].Y ? road[v].X: road[v].Y);
			ans[v] = last[v] = ans[u];
			upd(tin[v], 1);
			upd(tout[v], -1);	
		}
	}
	for(int v;q--;){
		scanf("%d", &v);
		printf("%d\n", ans[get_pr(v)]);
	}
}         

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |   scanf("%d %d", &x, &y), road[i] = MP(x, y);
      |   ~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   scanf("%d", &v);
      |   ~~~~~^~~~~~~~~~
synchronization.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |   scanf("%d", &v);
      |   ~~~~~^~~~~~~~~~

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