Submission #388657

#	Time	Username	Problem	Language	Result	Execution time	Memory
388657		aryan12	Synchronization (JOI13_synchronization)	C++17	100 / 100	744 ms	33656 KiB

synchronization

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

struct edge {
	int from, to;
};

const int N = 1e5 + 5;
vector<int> g[N];
int BIT[2 * N];
int tin[N], tout[N];
int tim = 0;
int DP[20][N];
bool isActive[N];

void dfs(int node, int par) {
	DP[0][node] = par;
	tin[node] = ++tim;
	for(int i = 0; i < g[node].size(); i++) {
		if(g[node][i] == par) {
			continue;
		}
		dfs(g[node][i], node);
	}
	tout[node] = ++tim;
}

void Update(int idx, int val) {
	for(int i = idx; i < 2 * N; i += (i & (-i))) {
		BIT[i] += val;
	}
}

int Query(int idx) {
	int ans = 0;
	for(int i = idx; i > 0; i -= (i & (-i))) {
		ans += BIT[i];
	}
	return ans;
}

int FindAncestor(int curNode) {
	int ancestor = curNode;
	int cnt = Query(tin[curNode]);
	for(int i = 19; i >= 0; i--) {
		if(DP[i][ancestor] != -1) {
			int thisCnt = Query(tin[DP[i][ancestor]]);
			if(thisCnt == cnt) {
				ancestor = DP[i][ancestor];
			}
		}
	}
	return ancestor;
}

void Solve() {
	for(int i = 0; i < 2 * N; i++) {
		BIT[i] = 0;
	}
	for(int i = 0; i < N; i++) {
		isActive[i] = false;
	}
	int n, m, q;
	cin >> n >> m >> q;
	vector<edge> edges(n);
	for(int i = 1; i < n; i++) {
		cin >> edges[i].from >> edges[i].to;
		g[edges[i].from].push_back(edges[i].to);
		g[edges[i].to].push_back(edges[i].from);
	}
	int UniqueInfo[n + 1], InfoBeforeDisconnect[n + 1];
	for(int i = 1; i <= n; i++) {
		UniqueInfo[i] = 1;
		InfoBeforeDisconnect[i] = 0;
	}
	dfs(1, -1);
	for(int i = 1; i <= n; i++) {
		Update(tin[i], 1);
		Update(tout[i], -1);
	}
	for(int i = 1; i < 20; i++) {
		for(int j = 1; j <= n; j++) {
			if(DP[i - 1][j] == -1)
				DP[i][j] = -1;
			else
				DP[i][j] = DP[i - 1][DP[i - 1][j]];
		}
	}
	for(int i = 1; i <= m; i++) {
		int edgeIdx;
		cin >> edgeIdx;
		int v = edges[edgeIdx].from, u = edges[edgeIdx].to;
		//cout << "edgeIdx = " << edgeIdx << ", v = " << v << ", u = " << u << "\n";
		if(DP[0][v] != u) {
			swap(v, u);
		}
		//u is the parent
		//cout << "v = " << v << ", u = " << u << ", ancestor = " << FindAncestor(u) << "\n";
		if(!isActive[edgeIdx]) {
			//making it active now
			int ancestor = FindAncestor(u);
			UniqueInfo[ancestor] += (UniqueInfo[v] - InfoBeforeDisconnect[v]);
			UniqueInfo[v] = UniqueInfo[ancestor];
			Update(tin[v], -1);
			Update(tout[v], 1);
		}
		else {
			//making it inactive now
			int ancestor = FindAncestor(v);
			UniqueInfo[v] = UniqueInfo[ancestor];
			InfoBeforeDisconnect[v] = UniqueInfo[v];
			Update(tin[v], 1);
			Update(tout[v], -1);
		}
		isActive[edgeIdx] = !isActive[edgeIdx];
	}
	while(q--) {
		int node;
		cin >> node;
		int ancestor = FindAncestor(node);
		cout << UniqueInfo[ancestor] << "\n";
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Solve();
	return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'void dfs(long long int, long long int)':
synchronization.cpp:20:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~

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