oj.uz

Submission #936819

# Submission time Handle Problem Language Result Execution time Memory
936819 2024-03-02T18:56:14 Z ParsaS Synchronization (JOI13_synchronization) C++17
0 / 100
 4157 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 = 4e5 + 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 10 ms 45656 KB Output is correct
2 Correct 9 ms 45724 KB Output is correct
3 Correct 10 ms 45724 KB Output is correct
4 Correct 10 ms 45656 KB Output is correct
5 Correct 10 ms 45660 KB Output is correct
6 Correct 23 ms 45788 KB Output is correct
7 Correct 257 ms 51284 KB Output is correct
8 Correct 257 ms 51264 KB Output is correct
9 Correct 271 ms 51212 KB Output is correct
10 Correct 3818 ms 117336 KB Output is correct
11 Correct 3953 ms 120800 KB Output is correct
12 Runtime error 2438 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 Runtime error 2498 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 45656 KB Output is correct
2 Correct 10 ms 45656 KB Output is correct
3 Correct 12 ms 45656 KB Output is correct
4 Correct 11 ms 45640 KB Output is correct
5 Correct 10 ms 45660 KB Output is correct
6 Correct 33 ms 45912 KB Output is correct
7 Correct 427 ms 75600 KB Output is correct
8 Runtime error 2423 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 2562 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 10 ms 45732 KB Output is correct
2 Correct 10 ms 45656 KB Output is correct
3 Correct 9 ms 45484 KB Output is correct
4 Correct 10 ms 45680 KB Output is correct
5 Correct 24 ms 45660 KB Output is correct
6 Correct 267 ms 51800 KB Output is correct
7 Correct 4157 ms 121580 KB Output is correct
8 Runtime error 2382 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -