oj.uz

Submission #936825

# Submission time Handle Problem Language Result Execution time Memory
936825 2024-03-02T18:59:53 Z ParsaS Synchronization (JOI13_synchronization) C++17
20 / 100
 4375 ms 262144 KB 
// In the name of God
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 1e6 + 5;
int n, m, q;
vector<int> qr[N];
vector<pair<int, int> > adj[N];
bool mark[N];
int sz[N], ans[N];
vector<int> ver, E;
int inx[N];
	
void dfs_sz(int v, int p = 0) {
	/*vector<pair<int, int> > stck;
	stck.pb(mp(v, 0));

	while (!stck.empty()) {
		int v = stck.back().fi, p = stck.back().se;
		if (sz[v] == 0) sz[v] = 1;
		bool ok = true;
		while (inx[v] < (int)adj[v].size()) {
			int u = adj[v][inx[v]].fi, i = adj[v][inx[v]].se;
			inx[v]++;

			if (u == p || mark[u]) continue;
			for (auto x : qr[i])
				E.pb(x);
			stck.pb(mp(u, v));
			ok = false;
			break;
		}
		if (ok && inx[v] == (int)adj[v].size()) {
			sz[p] += sz[v];
			stck.pop_back();
			inx[v] = 0;

		}
	}
	return;*/
	sz[v] = 1;
	for (auto [u, i] : adj[v]) {
		if (!mark[u] && u != p) {
			for (auto x : qr[i])
				E.pb(x);
			
			dfs_sz(u, v);
			sz[v] += sz[u];
		}
	}
}
	
int find_centroid(int v, int S, int p = 0) {
	for (auto [u, i] : adj[v]) {
		if (!mark[u] && u != p && sz[u] * 2 > S) {
			return find_centroid(u, S, v);
		}
	}
	return v;
}
	
int get(int val) {
	return lower_bound(E.begin(), E.end(), val) - E.begin();
}
	
vector<int> vec[N];
int T;
pair<int*, int> st[N << 4];
int stsz;
int inf = 1e9;
	
void rem(int S) {
	while (stsz > S) {
		*st[stsz-1].fi = st[stsz-1].se;
		stsz--;
	}
}
void SET(int& x, int y) {
	if (y > inf) return;
	st[stsz++] = mp(&x, x);
	x = y;
}
	
int lz[N << 2], seg[N << 2];
	
	
void shift(int v, int tl, int tr) {
	if (lz[v] == -1) return;
	if (lz[v]==0 || tl == tr)
		SET(seg[v], lz[v] * (tr - tl + 1));
	
	if (tl < tr) {
		SET(lz[v<<1], lz[v]);
		SET(lz[v << 1 | 1], lz[v]);
	}
	SET(lz[v], -1);
}
	
void set_val(int l, int r, int val, int v = 1, int tl = 0, int tr = E.size()) {
	if (l > r) return;
	
	shift(v, tl, tr);
	if (tl > r || tr < l) return;
	
	if (tl >= l && tr <= r) {
		SET(lz[v], val);
		shift(v, tl, tr);
		return;
	}
	int mid = (tl + tr) >> 1;
	set_val(l, r, val, v << 1, tl, mid);
	set_val(l, r, val, v << 1 | 1, mid + 1, tr);
	
	SET(seg[v], seg[v << 1] + seg[v << 1 | 1]);
}
int query(int l, int r, int v = 1, int tl = 0, int tr = E.size()) {
	if (l > r) return 0;
	shift(v, tl, tr);
	if (tl > r || tr < l) return 0;
	
	if (tl >= l && tr <= r) {
		return seg[v];
	}
	int mid = (tl + tr) >> 1;
	return query(l, r, v << 1, tl, mid) + query(l, r, v << 1 | 1, mid + 1, tr);
}
	
void dfs2(int v, int i, int p = 0) {
	int S = stsz;
	int prv = -1;
	for (int j = 0; j < (int)qr[i].size(); j += 2) {
		int x = get(qr[i][j]);
		set_val(get(prv + 1), x - 1, query(x, x));
		prv = qr[i][j + 1];
	}
	set_val(get(prv + 1), get(m + 1), inf);
	
	vec[T].pb(query(0, 0));
	
	for (auto [u, j] : adj[v]) {
		if (mark[u] || u == p) continue;
		dfs2(u, j, v);
	}
	
	
	rem(S);
}
	
void dfs3(int v, int i, int p = 0) {
	int S = stsz;
	int prv = -1;
	for (int j = 0; j < (int)qr[i].size(); j += 2) {
		int x = get(qr[i][j]);
		int y = query(get(prv + 1), x - 1) + query(x, x);
		set_val(get(prv + 1), x - 1, 0);
		set_val(x, x, y);
		prv = qr[i][j + 1];
	
	}
	set_val(get(prv + 1), get(m + 1), 0);
	ans[v] += query(0, get(m + 1));
	
	for (auto [u, j] : adj[v]) {
		if (mark[u] || u == p) continue;
		dfs3(u, j, v);
	}
	rem(S);
}
	
void dfs(int v) {
	rem(0);
	ver.clear();
	E.clear();
	E.pb(0);
	E.pb(m + 1);
	E.pb(m + 2);
	dfs_sz(v);
	
	
	int rt = find_centroid(v, sz[v]);
	mark[rt] = 1;
	
	sort(E.begin(), E.end());
	E.resize(unique(E.begin(), E.end()) - E.begin());
	
	int k = E.size();
	
	for (int i = 0; i < k; i++)
		set_val(i, i, i);
	int S = stsz;
	
	for (auto [u, i] : adj[rt]) {
		if (mark[u]) continue;
	
		rem(S);
	
		T = u;
		vec[T].clear();
	
		dfs2(u, i);
	
	}
	rem(0);
	set_val(0, 0, 1);
	for (auto [u, i] : adj[rt]) {
		if (mark[u]) continue;
		for (auto x : vec[u]) {
			if (x < inf)
				set_val(x, x, query(x, x) + 1);
		}
	}
	
	ans[rt] += query(0, m + 2);
	
	for (auto [u, i] : adj[rt]) {
		if (mark[u]) continue;
		S = stsz;
	
		for (auto x : vec[u])
			if (x < inf)
				set_val(x, x, query(x, x) - 1);
	
		dfs3(u, i);
	
		rem(S);
	}
	
	for (auto [u, i] : adj[rt]) {
		if (!mark[u]) dfs(u);
	}
}
	
void solve() {
	cin >> n >> m >> q;
	for (int i = 1; i <= n - 1; i++) {
		int v, u; cin >> v >> u;
		adj[v].pb(mp(u, i)), adj[u].pb(mp(v, i));
	}

	for (int i = 1; i <= m; i++) {
		int k; cin >> k;
		qr[k].pb(i);
	}
	for (int i = 1; i < n; i++) {
		if ((int)qr[i].size() % 2)
			qr[i].pb(m + 1);
	}
	
	memset(lz, -1, sizeof lz);
	dfs(1);

	while (q--) {
		int c; cin >> c;
		cout << ans[c] << '\n';
	}
}
	
int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("input.in", "r", stdin);
	int tc = 1; // cin >> tc;
	while (tc--) {
		solve();
	}
	
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 96340 KB Output is correct
2 Correct 20 ms 96344 KB Output is correct
3 Correct 21 ms 96348 KB Output is correct
4 Correct 20 ms 96348 KB Output is correct
5 Correct 20 ms 96348 KB Output is correct
6 Correct 34 ms 96348 KB Output is correct
7 Correct 268 ms 102244 KB Output is correct
8 Correct 261 ms 101924 KB Output is correct
9 Correct 274 ms 101972 KB Output is correct
10 Correct 3744 ms 168876 KB Output is correct
11 Correct 3996 ms 169196 KB Output is correct
12 Runtime error 195 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2336 ms 234488 KB Output is correct
2 Correct 2270 ms 233144 KB Output is correct
3 Correct 3447 ms 257128 KB Output is correct
4 Correct 3480 ms 258632 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 96348 KB Output is correct
2 Correct 20 ms 96600 KB Output is correct
3 Correct 23 ms 96344 KB Output is correct
4 Correct 21 ms 96296 KB Output is correct
5 Correct 21 ms 96348 KB Output is correct
6 Correct 45 ms 98752 KB Output is correct
7 Correct 453 ms 126036 KB Output is correct
8 Runtime error 208 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 195 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 96348 KB Output is correct
2 Correct 22 ms 96412 KB Output is correct
3 Correct 26 ms 94544 KB Output is correct
4 Correct 25 ms 91480 KB Output is correct
5 Correct 48 ms 92084 KB Output is correct
6 Correct 268 ms 98532 KB Output is correct
7 Correct 4375 ms 165972 KB Output is correct
8 Runtime error 280 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -