oj.uz

Submission #598223

# Submission time Handle Problem Language Result Execution time Memory
598223 2022-07-17T19:56:42 Z penguinhacker Synchronization (JOI13_synchronization) C++17
40 / 100
 8000 ms 17564 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], p[mxN], edge[mxN], last[mxN], ans[mxN];
vector<int> adj[mxN];
bool active[mxN];

void dfs(int u=0) {
	for (int i : adj[u]) {
		int v=eu[i]^ev[i]^u;
		if (v!=p[u]) {
			p[v]=u;
			edge[i]=v;
			dfs(v);
		}
	}
}

int get_head(int u) {
	for (; u&&active[u]; u=p[u]);
	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];
		//cout << "activatting " << u << endl;
		if (!active[u]) { // activate edge between u-p[u]
			int v=get_head(p[u]);
			ans[v]+=ans[u]-last[u];
		} else {
			ans[u]=ans[get_head(u)];
			last[u]=ans[u];
		}
		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 3 ms 2688 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 3 ms 2680 KB Output is correct
5 Correct 3 ms 2708 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 8 ms 3392 KB Output is correct
8 Correct 7 ms 3412 KB Output is correct
9 Correct 9 ms 3472 KB Output is correct
10 Correct 80 ms 10628 KB Output is correct
11 Correct 101 ms 10524 KB Output is correct
12 Correct 52 ms 16716 KB Output is correct
13 Correct 41 ms 10552 KB Output is correct
14 Correct 72 ms 9676 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8029 ms 13292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 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 2684 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 8 ms 4100 KB Output is correct
8 Correct 67 ms 17540 KB Output is correct
9 Correct 92 ms 17540 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 17484 KB Output is correct
2 Correct 6841 ms 16904 KB Output is correct
3 Correct 6627 ms 16976 KB Output is correct
4 Correct 6891 ms 17008 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 8 ms 3456 KB Output is correct
7 Correct 118 ms 11468 KB Output is correct
8 Correct 97 ms 17564 KB Output is correct
9 Correct 56 ms 11560 KB Output is correct
10 Correct 97 ms 10904 KB Output is correct
11 Execution timed out 8067 ms 13204 KB Time limit exceeded
12 Halted 0 ms 0 KB -