oj.uz

Submission #936820

# Submission time Handle Problem Language Result Execution time Memory
936820 2024-03-02T18:57:04 Z ParsaS Synchronization (JOI13_synchronization) C++17
20 / 100
 4099 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 23 ms 96348 KB Output is correct
2 Correct 20 ms 96348 KB Output is correct
3 Correct 21 ms 96344 KB Output is correct
4 Correct 21 ms 96348 KB Output is correct
5 Correct 23 ms 96600 KB Output is correct
6 Correct 34 ms 96356 KB Output is correct
7 Correct 264 ms 102128 KB Output is correct
8 Correct 259 ms 102116 KB Output is correct
9 Correct 274 ms 102412 KB Output is correct
10 Correct 3865 ms 171256 KB Output is correct
11 Correct 4037 ms 170196 KB Output is correct
12 Runtime error 204 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 2355 ms 236672 KB Output is correct
2 Correct 2329 ms 234844 KB Output is correct
3 Correct 3497 ms 258812 KB Output is correct
4 Correct 3433 ms 258836 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 96344 KB Output is correct
2 Correct 21 ms 96348 KB Output is correct
3 Correct 21 ms 96444 KB Output is correct
4 Correct 21 ms 96348 KB Output is correct
5 Correct 21 ms 96468 KB Output is correct
6 Correct 45 ms 98724 KB Output is correct
7 Correct 430 ms 126036 KB Output is correct
8 Runtime error 228 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 192 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 20 ms 96208 KB Output is correct
3 Correct 20 ms 96348 KB Output is correct
4 Correct 21 ms 96348 KB Output is correct
5 Correct 35 ms 96556 KB Output is correct
6 Correct 268 ms 102060 KB Output is correct
7 Correct 4099 ms 169232 KB Output is correct
8 Runtime error 205 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -