oj.uz

Submission #937036

# Submission time Handle Problem Language Result Execution time Memory
937036 2024-03-03T09:10:09 Z ParsaS Synchronization (JOI13_synchronization) C++17
20 / 100
 3698 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 20 ms 97884 KB Output is correct
2 Correct 20 ms 97884 KB Output is correct
3 Correct 20 ms 97884 KB Output is correct
4 Correct 21 ms 97884 KB Output is correct
5 Correct 20 ms 97884 KB Output is correct
6 Correct 34 ms 98140 KB Output is correct
7 Correct 247 ms 103368 KB Output is correct
8 Correct 244 ms 103508 KB Output is correct
9 Correct 263 ms 103364 KB Output is correct
10 Correct 3448 ms 166900 KB Output is correct
11 Correct 3589 ms 166916 KB Output is correct
12 Runtime error 239 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 2217 ms 226140 KB Output is correct
2 Correct 2188 ms 224640 KB Output is correct
3 Correct 3269 ms 243524 KB Output is correct
4 Correct 3256 ms 243280 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 98000 KB Output is correct
2 Correct 20 ms 97884 KB Output is correct
3 Correct 22 ms 97884 KB Output is correct
4 Correct 21 ms 98048 KB Output is correct
5 Correct 21 ms 97884 KB Output is correct
6 Correct 42 ms 98172 KB Output is correct
7 Correct 398 ms 118636 KB Output is correct
8 Runtime error 233 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 242 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 97884 KB Output is correct
2 Correct 20 ms 97884 KB Output is correct
3 Correct 20 ms 97880 KB Output is correct
4 Correct 21 ms 97880 KB Output is correct
5 Correct 34 ms 98336 KB Output is correct
6 Correct 258 ms 103504 KB Output is correct
7 Correct 3698 ms 167204 KB Output is correct
8 Runtime error 231 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -