oj.uz

Submission #349055

# Submission time Handle Problem Language Result Execution time Memory
349055 2021-01-16T12:59:36 Z cheissmart Synchronization (JOI13_synchronization) C++14
100 / 100
 311 ms 27884 KB 
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7;

vi G[N];
int p[N][20], on[N], tin[N], tout[N], tt, ans[N], last[N];

void dfs(int u, int pa = 0) {
	tin[u] = ++tt;
	p[u][0] = pa;
	for(int i = 1; i < 20; i++)
		p[u][i] = p[p[u][i - 1]][i - 1];
	for(int v:G[u]) if(v != pa)
		dfs(v, u);
	tout[u] = tt;
}

int bit[N];

void add(int pos, int val) {
	for(; pos < N; pos += pos & -pos)
		bit[pos] += val;
}

void add(int l, int r, int val) {
	add(l, val);
	add(r + 1, -val);
}

int qry(int pos) {
	int res = 0;
	for(; pos; pos -= pos & -pos)
		res += bit[pos];
	return res;
}

int find(int u) {
	int tt = qry(tin[u]);
	for(int j = 19; j >= 0; j--)
		if(p[u][j] && qry(tin[p[u][j]]) == tt)
			u = p[u][j];
	return u;
}

signed main()
{
	IO_OP;

	int n, m, q;
	cin >> n >> m >> q;
	vi u(m), v(m);
	for(int i = 0; i < n - 1; i++) {
		cin >> u[i] >> v[i];
		G[u[i]].PB(v[i]);
		G[v[i]].PB(u[i]);
	}
	dfs(1);
	for(int i = 1; i <= n; i++) {
		add(tin[i], tout[i], 1);
		ans[i] = 1;
	}

	while(m--) {
		int d;
		cin >> d;
		d--;
		int x = (p[u[d]][0] == v[d] ? u[d] : v[d]);
		if(on[d]) { // cut
			int y = find(x);
			assert(x != y);
			last[x] = ans[x] = ans[y];
			add(tin[x], tout[x], 1);
		} else { // link
			int y = find(p[x][0]);
			int nw = ans[x] + ans[y] - last[x];
			ans[y] = nw;
			add(tin[x], tout[x], -1);
		}
		on[d] ^= 1;
	}
	while(q--) {
		int u;
		cin >> u;
		cout << ans[find(u)] << '\n';
	}


}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 3 ms 5100 KB Output is correct
3 Correct 3 ms 5100 KB Output is correct
4 Correct 3 ms 5100 KB Output is correct
5 Correct 3 ms 5100 KB Output is correct
6 Correct 4 ms 5228 KB Output is correct
7 Correct 16 ms 6764 KB Output is correct
8 Correct 16 ms 6764 KB Output is correct
9 Correct 16 ms 6764 KB Output is correct
10 Correct 227 ms 22508 KB Output is correct
11 Correct 212 ms 22380 KB Output is correct
12 Correct 247 ms 27092 KB Output is correct
13 Correct 122 ms 22372 KB Output is correct
14 Correct 152 ms 20588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 24300 KB Output is correct
2 Correct 99 ms 24044 KB Output is correct
3 Correct 115 ms 25232 KB Output is correct
4 Correct 115 ms 25324 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 3 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 5 ms 5356 KB Output is correct
7 Correct 23 ms 7276 KB Output is correct
8 Correct 311 ms 27756 KB Output is correct
9 Correct 299 ms 27756 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 27884 KB Output is correct
2 Correct 175 ms 26448 KB Output is correct
3 Correct 175 ms 26476 KB Output is correct
4 Correct 173 ms 26476 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 3 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 20 ms 6892 KB Output is correct
7 Correct 266 ms 23276 KB Output is correct
8 Correct 297 ms 27756 KB Output is correct
9 Correct 138 ms 23396 KB Output is correct
10 Correct 184 ms 21904 KB Output is correct
11 Correct 133 ms 25452 KB Output is correct
12 Correct 133 ms 25560 KB Output is correct
13 Correct 173 ms 26524 KB Output is correct