Submission #1185039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185039		nguyn	Synchronization (JOI13_synchronization)	C++20	100 / 100	174 ms	26172 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 2e5 + 5;

int n, m, q;
vector<int> g[N]; 
pii e[N]; 
int tin[N], tout[N], h[N], bit[N];
int timedfs; 
int up[N][20];
int del[N]; 
int res[N], lst[N]; 

void update(int id, int val) {
	for (int i = id; i <= n; i += (i & -i)) bit[i] += val; 
}

int get(int id) {
	int res = 0;
	for (int i = id; i > 0; i -= (i & -i)) res += bit[i];
	return res; 
}

void pre_dfs(int u, int p) {
	res[u] = 1;
	tin[u] = ++timedfs; 
	for (int v : g[u]) {
		if (v == p) continue; 
		up[v][0] = u; 
		for (int i = 1; i < 20; i++) up[v][i] = up[up[v][i - 1]][i - 1];
		h[v] = h[u] + 1;
		pre_dfs(v, u); 
	}
	tout[u] = timedfs;
}


int find(int u) {
	for (int i = 19; i >= 0; i--) {
		if (get(tin[up[u][i]]) == get(tin[u])) {
			u = up[u][i]; 
		}
	}
	return u; 
}

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n >> m >> q; 
    for (int i = 1; i < n; i++) {
    	int u, v; cin >> u >> v;
    	g[u].pb(v);
    	g[v].pb(u);
    	e[i] = {u, v}; 
    }
    pre_dfs(1, 0);
    for (int i = 1; i <= n; i++) {
    	update(tin[i], -1);
    	update(tout[i] + 1, 1);
    }
    for (int i = 1; i <= m; i++) {
    	int id;
    	cin >> id; 
    	int u = e[id].F;
    	int v = e[id].S;
    	if (h[u] > h[v]) swap(u, v); 
    	if (!del[id]) {
    		res[find(u)] += res[v] - lst[v]; 
    		update(tin[v], 1);
    		update(tout[v] + 1, -1); 
    	} 	
    	else {
    		res[v] = lst[v] = res[find(u)]; 
    		update(tin[v], -1);
    		update(tout[v] + 1, 1); 
    	}
    	del[id] ^= 1;
    }
    for (int i = 1; i <= q; i++) {
    	int u; cin >> u;
    	cout << res[find(u)] << '\n'; 
    }
}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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