oj.uz

Submission #937029

# Submission time Handle Problem Language Result Execution time Memory
937029 2024-03-03T09:06:11 Z ParsaS Synchronization (JOI13_synchronization) C++17
20 / 100
 3840 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 = 2e5 + 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 = 7e7;
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 4 ms 21852 KB Output is correct
2 Correct 5 ms 21852 KB Output is correct
3 Correct 4 ms 21852 KB Output is correct
4 Correct 5 ms 21848 KB Output is correct
5 Correct 6 ms 21852 KB Output is correct
6 Correct 19 ms 24148 KB Output is correct
7 Correct 233 ms 29416 KB Output is correct
8 Correct 225 ms 29408 KB Output is correct
9 Correct 243 ms 29520 KB Output is correct
10 Correct 3567 ms 93364 KB Output is correct
11 Correct 3685 ms 93400 KB Output is correct
12 Runtime error 296 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 2241 ms 151432 KB Output is correct
2 Correct 2234 ms 149920 KB Output is correct
3 Correct 3282 ms 170732 KB Output is correct
4 Correct 3273 ms 170632 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21848 KB Output is correct
2 Correct 4 ms 21852 KB Output is correct
3 Correct 6 ms 24100 KB Output is correct
4 Correct 6 ms 23900 KB Output is correct
5 Correct 5 ms 21852 KB Output is correct
6 Correct 27 ms 24232 KB Output is correct
7 Correct 382 ms 44872 KB Output is correct
8 Runtime error 320 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 298 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 4 ms 21848 KB Output is correct
2 Correct 5 ms 21852 KB Output is correct
3 Correct 4 ms 21852 KB Output is correct
4 Correct 6 ms 24104 KB Output is correct
5 Correct 18 ms 24156 KB Output is correct
6 Correct 235 ms 29444 KB Output is correct
7 Correct 3840 ms 94060 KB Output is correct
8 Runtime error 297 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -