Submission #1287194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287194		hminhat	Synchronization (JOI13_synchronization)	C++20	100 / 100	605 ms	24648 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define FOR(i, x, y)    for(int i = x, _y = y; i <= _y; i++)
#define FOD(i, x, y)    for(int i = x, _y = y; i >= _y; i--)
#define emp emplace
#define emb emplace_back
#define emf emplace_front
#define fi first
#define se second
#define el "\n"
#define all(V) V.begin(), V.end()

template<typename X,typename Y>bool tmax(X& x,Y y){if(x<y){x=y;return 1;}return 0;}
template<typename X,typename Y>bool tmin(X& x,Y y){if(x>y){x=y;return 1;}return 0;}

void file() {
	#define NAME "TEST"
	if(fopen(NAME".inp", "r")){freopen(NAME".inp", "r", stdin);freopen(NAME".ans", "w", stdout);}
	else {
		#undef NAME
		#define NAME "C:\\Users\\PC\\Documents\\NhatBeoCode\\AIO\\Test"
		if(fopen(NAME".inp", "r")){freopen(NAME".inp", "r", stdin);freopen(NAME".out", "w", stdout);}
	}
}

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll L, ll R) { return L + 1LL * rd() * rd() % (R - L + 1); }

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

int n, m, q, dd[nmax], w[nmax], h[nmax], up[17][nmax], child[nmax], sz[nmax];
vector<pii> E;
vector<int> g[nmax];

void dfs(int u, int pre) {
	child[u] = 1;
	for(int v : g[u]) {
		if(v == pre)	continue;
		h[v] = h[u] + 1;
		up[0][v] = u;
		FOR(i, 1, 16) {
			up[i][v] = up[i - 1][up[i - 1][v]];
		}
		dfs(v, u);
		child[u] += child[v];
	}
}

struct BIT {

	int B[nmax];

	void update(int u, int val) {
		for(;u <= n; u += u & (-u)) {
			B[u] += val;
		}
	}

	int get(int u) {
		int res = 0;
		for(;u >= 1; u -= u & (-u)) {
			res += B[u];
		}
		return res;
	}

	int get(int l, int r) {
		return get(r) - get(l - 1);
	}

} T;

int cur = 1, chainID[nmax], idx = 1, pos[nmax], chainPar[nmax];

void hld(int u, int pre) {
	if(chainPar[cur] == 0) {
		chainPar[cur] = u;
	}
	chainID[u] = cur;
	pos[u] = idx++;
	int nxt = 0;
	for(int v : g[u]) {
		if(v == pre)	continue;
		if(nxt == 0 || child[v] > child[nxt]) {
			nxt = v;
		}
	}
	if(nxt) {
		hld(nxt, u);
	}
	for(int v : g[u]) {
		if(v == pre || v == nxt)	continue;
		cur++;
		hld(v, u);
	}
}

int jump(int u, int k) {
	FOR(i, 0, 16) {
		if(k >> i & 1) {
			u = up[i][u];
		}
	}
	return u;
}

int check(int u, int v) {
	int ans = 0;
	while(chainID[u] != chainID[v]) {
		ans += T.get(pos[chainPar[chainID[u]]], pos[u]);
		u = up[0][chainPar[chainID[u]]];
	}
	if(pos[u] > pos[v])	swap(u, v);
	ans += T.get(pos[u] + 1, pos[v]);
	return ans;
}

int get(int u) {
	int l = 0, r = h[u], res = 0;
	while(l <= r) {
		int mid = (l + r) >> 1;
		int v = jump(u, mid), ans = check(u, v);
		// cout << u << ' ' << v << ' ' << ans << el;
		if(ans == h[u] - h[v]) {
			l = mid + 1;
			res = v;
		}
		else {
			r = mid - 1;
		}
	}
	return res;
}

void connect(int id) {
	int u = E[id].fi, v = E[id].se;
	if(h[u] > h[v])	swap(u, v);
	// cout << u << ' ' << v << ' ';
	u = get(u);
	// cout << u << ' ';
	sz[u] += sz[v] - w[id];
	// cout << sz[u] << el;
}

void disconnect(int id) {
	int u = E[id].fi, v = E[id].se;
	if(h[u] > h[v])	swap(u, v);
	// cout << u << ' ' << v << ' ';
	u = get(u);
	// cout << u << ' ';
	w[id] = sz[v] = sz[u];
	// cout << sz[v] << el;
}

int main()
{
	file();
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> q;
	FOR(i, 1, n - 1) {
		int u, v;
		cin >> u >> v;
		E.emb(u, v);
		g[u].emb(v);
		g[v].emb(u);
	}
	FOR(i, 1, n) {
		sz[i] = 1;
	}
	dfs(1, 0);
	hld(1, 0);
	while(m -- ) {
		int id;
		cin >> id;
		id--;
		int u = E[id].fi, v = E[id].se;
		if(h[u] > h[v])	swap(u, v);
		!dd[id] ? T.update(pos[v], 1) : T.update(pos[v], -1);
		!dd[id] ? connect(id) : disconnect(id);
		dd[id] ^= 1;
	}
	FOR(i, 1, q) {
		int x;
		cin >> x;
		cout << sz[get(x)] << el;
	}
	return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'void file()':
synchronization.cpp:25:43: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         if(fopen(NAME".inp", "r")){freopen(NAME".inp", "r", stdin);freopen(NAME".ans", "w", stdout);}
      |                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:25:75: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         if(fopen(NAME".inp", "r")){freopen(NAME".inp", "r", stdin);freopen(NAME".ans", "w", stdout);}
      |                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:29:51: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |                 if(fopen(NAME".inp", "r")){freopen(NAME".inp", "r", stdin);freopen(NAME".out", "w", stdout);}
      |                                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:29:83: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |                 if(fopen(NAME".inp", "r")){freopen(NAME".inp", "r", stdin);freopen(NAME".out", "w", stdout);}
      |                                                                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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