oj.uz

Submission #937032

# Submission time Handle Problem Language Result Execution time Memory
937032 2024-03-03T09:08:31 Z ParsaS Synchronization (JOI13_synchronization) C++17
20 / 100
 3809 ms 262144 KB 
// In the name of God
#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];
int ver[N], E[N], szver, szE;

void dfs_sz(int& v, int p, int i = -1) {
	sz[v] = 1;
	ver[szver++] = v;
	if (i >= 0) {
		for (int j = 0; j < (int)qr[i].size(); j++)
			E[szE++] = qr[i][j];
	}
	for (auto& a : adj[v]) {
		if (!mark[a.fi] && a.fi != p) {
			
			dfs_sz(a.fi, v, a.se);
			sz[v] += sz[a.fi];
			
		}
	}
}

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;
}

inline int get(int val) {
	return lower_bound(E, E + szE, val) - E;
}

const int M = 1e8;
vector<int> vec[N];
int T;
pair<int*, int> st[M];
int stsz;
int inf = 1e9;

void rem(int S) {
	while (stsz > S) {
		*st[stsz-1].fi = st[stsz-1].se;
		stsz--;
	}
}
inline void SET(int& x, int y) {
	if (y > inf || x == y) return;
	//assert(stsz < M);
	st[stsz++] = mp(&x, x);
	x = y;
}
bool ISSUM;
int lz[N << 2], seg[N << 2];


void shift(int v, int tl, int tr) {
	if (lz[v] == -1) return;
	if ((lz[v]==0 && ISSUM) || 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 = szE) {
	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 = szE) {
	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);
	szver = 0;
	szE = 0;
	E[szE++] = 0;
	E[szE++] = m + 1;
	E[szE++] = m + 2;
	dfs_sz(v, 0);
	
	int rt = find_centroid(v, sz[v]);
	mark[rt] = 1;

	sort(E, E + szE);
	szE = unique(E, E + szE) - E;

	int k = szE;

	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);
	ISSUM = true;
	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);
	}
	ISSUM = false;

	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("input2.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 45 ms 86352 KB Output is correct
2 Correct 35 ms 86360 KB Output is correct
3 Correct 39 ms 86356 KB Output is correct
4 Correct 37 ms 86540 KB Output is correct
5 Correct 37 ms 86608 KB Output is correct
6 Correct 50 ms 87208 KB Output is correct
7 Correct 268 ms 93524 KB Output is correct
8 Correct 261 ms 93572 KB Output is correct
9 Correct 271 ms 103508 KB Output is correct
10 Correct 3619 ms 166652 KB Output is correct
11 Correct 3809 ms 167856 KB Output is correct
12 Runtime error 248 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 2252 ms 226184 KB Output is correct
2 Correct 2222 ms 218928 KB Output is correct
3 Correct 3245 ms 243536 KB Output is correct
4 Correct 3265 ms 243416 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 97884 KB Output is correct
2 Correct 22 ms 97884 KB Output is correct
3 Correct 21 ms 97884 KB Output is correct
4 Correct 23 ms 98024 KB Output is correct
5 Correct 21 ms 97884 KB Output is correct
6 Correct 42 ms 98188 KB Output is correct
7 Correct 393 ms 118608 KB Output is correct
8 Runtime error 238 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 236 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 98008 KB Output is correct
2 Correct 20 ms 97884 KB Output is correct
3 Correct 21 ms 98000 KB Output is correct
4 Correct 22 ms 97884 KB Output is correct
5 Correct 37 ms 98128 KB Output is correct
6 Correct 254 ms 103508 KB Output is correct
7 Correct 3737 ms 167168 KB Output is correct
8 Runtime error 237 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -