oj.uz

Submission #936828

# Submission time Handle Problem Language Result Execution time Memory
936828 2024-03-02T19:01:04 Z ParsaS Synchronization (JOI13_synchronization) C++17
0 / 100
 8000 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 29 ms 94288 KB Output is correct
2 Correct 20 ms 94300 KB Output is correct
3 Correct 22 ms 94300 KB Output is correct
4 Correct 23 ms 94300 KB Output is correct
5 Correct 33 ms 94376 KB Output is correct
6 Correct 38 ms 94300 KB Output is correct
7 Correct 314 ms 99928 KB Output is correct
8 Correct 299 ms 100176 KB Output is correct
9 Correct 310 ms 99920 KB Output is correct
10 Correct 4422 ms 168556 KB Output is correct
11 Correct 4417 ms 168300 KB Output is correct
12 Runtime error 214 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 Execution timed out 8039 ms 230836 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 94296 KB Output is correct
2 Correct 20 ms 94300 KB Output is correct
3 Correct 21 ms 94416 KB Output is correct
4 Correct 22 ms 94300 KB Output is correct
5 Correct 21 ms 94300 KB Output is correct
6 Correct 85 ms 96644 KB Output is correct
7 Execution timed out 8055 ms 132640 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 201 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 94300 KB Output is correct
2 Correct 20 ms 94248 KB Output is correct
3 Correct 20 ms 94300 KB Output is correct
4 Correct 22 ms 94420 KB Output is correct
5 Correct 39 ms 94768 KB Output is correct
6 Correct 314 ms 99924 KB Output is correct
7 Correct 4776 ms 168696 KB Output is correct
8 Runtime error 204 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -