oj.uz

Submission #936826

# Submission time Handle Problem Language Result Execution time Memory
936826 2024-03-02T19:00:12 Z ParsaS Synchronization (JOI13_synchronization) C++17
0 / 100
 4167 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 = 5e5 + 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 12 ms 53336 KB Output is correct
2 Correct 11 ms 53444 KB Output is correct
3 Correct 18 ms 43356 KB Output is correct
4 Correct 18 ms 43356 KB Output is correct
5 Correct 21 ms 43612 KB Output is correct
6 Correct 34 ms 44120 KB Output is correct
7 Correct 261 ms 50620 KB Output is correct
8 Correct 258 ms 50444 KB Output is correct
9 Correct 274 ms 50692 KB Output is correct
10 Correct 3978 ms 118136 KB Output is correct
11 Correct 4167 ms 126496 KB Output is correct
12 Runtime error 2405 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2330 ms 192932 KB Output is correct
2 Correct 2278 ms 190788 KB Output is correct
3 Runtime error 2311 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 53340 KB Output is correct
2 Correct 12 ms 53340 KB Output is correct
3 Correct 12 ms 53340 KB Output is correct
4 Correct 11 ms 53476 KB Output is correct
5 Correct 11 ms 53340 KB Output is correct
6 Correct 34 ms 55644 KB Output is correct
7 Correct 422 ms 85076 KB Output is correct
8 Runtime error 2371 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 2359 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 11 ms 53336 KB Output is correct
2 Correct 12 ms 53340 KB Output is correct
3 Correct 10 ms 53340 KB Output is correct
4 Correct 12 ms 53340 KB Output is correct
5 Correct 25 ms 53592 KB Output is correct
6 Correct 256 ms 61008 KB Output is correct
7 Correct 3967 ms 128496 KB Output is correct
8 Runtime error 2434 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -