oj.uz

Submission #598238

# Submission time Handle Problem Language Result Execution time Memory
598238 2022-07-17T20:24:52 Z penguinhacker Synchronization (JOI13_synchronization) C++17
100 / 100
 280 ms 26888 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, m, q, eu[mxN], ev[mxN], edge[mxN], last[mxN], ans[mxN], tin[mxN], tout[mxN], t, d[mxN], anc[mxN][17], ft[2*mxN+1];
vector<int> adj[mxN];
bool active[mxN];

void dfs(int u=0) {
	tin[u]=t++;
	for (int i=1; i<17; ++i)
		anc[u][i]=anc[anc[u][i-1]][i-1];
	for (int i : adj[u]) {
		int v=eu[i]^ev[i]^u;
		if (v!=anc[u][0]) {
			d[v]=d[u]+1, anc[v][0]=u;
			edge[i]=v;
			dfs(v);
		}
	}
	tout[u]=t++;
}

void upd(int i, int x) {
	for (++i; i<=2*n; i+=i&-i)
		ft[i]+=x;
}

int qry(int i) {
	int r=0;
	for (++i; i; i-=i&-i)
		r+=ft[i];
	return r;
}

int get_head(int u) {
	for (int i=16; ~i; --i)
		if (qry(tin[u])-qry(tin[anc[u][i]])==(1<<i))
			u=anc[u][i];
	return u;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	for (int i=1; i<n; ++i) {
		cin >> eu[i] >> ev[i], --eu[i], --ev[i];
		adj[eu[i]].push_back(i);
		adj[ev[i]].push_back(i);
	}
	dfs();
	fill(ans, ans+n, 1);
	while(m--) {
		int u;
		cin >> u;
		u=edge[u];
		if (!active[u]) { // activate edge between u-p[u]
			int v=get_head(anc[u][0]);
			ans[v]+=ans[u]-last[u];
			//cout << v << " " << qry(tin[p[u]]) << endl;
		} else {
			ans[u]=ans[get_head(u)];
			last[u]=ans[u];
			//cout << get_head(u) << endl;
		}
		upd(tin[u], active[u]?-1:1);
		upd(tout[u], active[u]?1:-1);
		active[u]^=1;
	}
	while(q--) {
		int u;
		cin >> u, --u;
		cout << ans[get_head(u)] << "\n";
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 4 ms 2872 KB Output is correct
7 Correct 14 ms 4180 KB Output is correct
8 Correct 13 ms 4240 KB Output is correct
9 Correct 17 ms 4308 KB Output is correct
10 Correct 232 ms 17832 KB Output is correct
11 Correct 223 ms 17772 KB Output is correct
12 Correct 228 ms 25504 KB Output is correct
13 Correct 119 ms 18096 KB Output is correct
14 Correct 144 ms 17328 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 21580 KB Output is correct
2 Correct 105 ms 22076 KB Output is correct
3 Correct 95 ms 25580 KB Output is correct
4 Correct 95 ms 25596 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2680 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2900 KB Output is correct
7 Correct 18 ms 5076 KB Output is correct
8 Correct 267 ms 25744 KB Output is correct
9 Correct 244 ms 25736 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 25752 KB Output is correct
2 Correct 161 ms 25648 KB Output is correct
3 Correct 173 ms 25832 KB Output is correct
4 Correct 154 ms 25976 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2680 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 18 ms 4356 KB Output is correct
7 Correct 280 ms 18128 KB Output is correct
8 Correct 259 ms 25668 KB Output is correct
9 Correct 152 ms 18652 KB Output is correct
10 Correct 186 ms 18056 KB Output is correct
11 Correct 129 ms 22736 KB Output is correct
12 Correct 159 ms 23472 KB Output is correct
13 Correct 153 ms 26888 KB Output is correct