oj.uz

Submission #528450

# Submission time Handle Problem Language Result Execution time Memory
528450 2022-02-20T10:19:14 Z iliaM Inside information (BOI21_servers) C++17
50 / 100
 425 ms 56640 KB 
#include <bits/stdc++.h>
using namespace std;
#define cerr cerr << "DEBUG "

constexpr int N = 3e5 + 10;

int n, k;
vector<pair<int, int>> qp[N];
vector<int> qu[N];
vector<pair<int, int>> up, down;
vector<int> verts;
int sz[N];
vector<pair<int, int>> g[N];
bool used[N];
long long ans[N];
int mark[N];
pair<int, int> tmp[N];
bool has[N];

int centroid(int v, int p, int m) {
	has[v] = true;
	verts.push_back(v);
	int ret = 0, cool = 1;
	sz[v] = 1;
	for (auto &e : g[v]) {
		int u = e.first;
		if (u != p && !used[u]) {
			ret ^= ~centroid(u, v, m);
			cool &= sz[u] <= m / 2;
			sz[v] += sz[u];
		}
	}
	return cool && m - sz[v] <= m / 2 ? v : ~ret;
}


void dfs(int v, int p, int fe, int f, int s) {
	sz[v] = 1;
	if (~f) {
		for (auto &query : qu[v]) {
			if (fe > query) {
				continue;
			}
			up.push_back({fe, query});
		}
		mark[v] = fe;
	}
	if (~s) {
		down.push_back({fe, s});
		tmp[v] = make_pair(fe, s);
		assert(s >= fe);
	}
	for (auto &e : g[v]) {
		int u = e.first, w = e.second;
		if (u != p && !used[u]) {
			dfs(u, v, fe, f == -1 || w >= f ? -1 : w, s == -1 || w <= s ? -1 : w);
			sz[v] += sz[u];
		}
	}
}

int fen[N];

void update(int i, int x) {
	for (++i; i < N; i += i & -i) {
		fen[i] += x;
	}
}

int query(int i) {
	int ret = 0;
	for (++i; i > 0; i -= i & -i) {
		ret += fen[i];
	}
	return ret;
}

void solve() {
	static vector<int> vec[N];
	auto &a = up, &b = down;
	for (int i = 0; i < (int) b.size(); ++i) {
		vec[i].clear();
	}

	for (auto &x : a) {
		auto p = upper_bound(b.begin(), b.end(), make_pair(x.first, INT_MAX));
		ans[x.second]++; // for centroid
		if (p != b.end()) {
			vec[p - b.begin()].push_back(x.second);
		}
	}

	for (int i = (int) b.size() - 1; i >= 0; --i) {
		update(b[i].second, +1);
		for (auto &x : vec[i]) {
			ans[x] += query(x);
		}
	}
	for (auto &x : b) {
		update(x.second, -1);
	}
}

void decompose(int v, int m) {
	int cent = centroid(v, -1, m);
	
	up.clear();
	down.clear();
	
	sz[cent] = 1;
	for (auto &e : g[cent]) {
		int u = e.first, w = e.second;
		if (!used[u]) {
			dfs(u, cent, w, w, w);
			sz[cent] += sz[u];
		}
	}
	
	// calc for pairs in subtrees
	sort(down.begin(), down.end());
	solve();
	
	assert((int) verts.size() == sz[cent]);

	for (auto &u : verts) {
		for (auto &query : qp[u]) {
			if (!has[query.first]) {
				continue;
			}
			if (u == cent) {
				ans[query.second] += query.first == u ||
					(tmp[query.first].second < query.second);
			} else if (~mark[u]) {
				if (query.first == cent) {
					ans[query.second] += mark[u] < query.second;
				} else {
					ans[query.second] += mark[u] < tmp[query.first].first &&
						tmp[query.first].second < query.second;
				}
			}
		}
	}

	// calc for pairs from centroid
	for (auto &query : qu[cent]) {
		ans[query] += 1 + down.size();
	}

	for (auto &u : verts) {
		mark[u] = -1;
		tmp[u] = make_pair(-1, INT_MAX);
		has[u] = false;
	}
	verts.clear();
	used[cent] = true;
	for (auto &e : g[cent]) {
		int u = e.first;
		if (!used[u]) {
			decompose(u, sz[u]);
		}
	}
}

int qtype[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	memset(mark, -1, sizeof(mark));
	for (int i = 0; i < N; ++i) {
		tmp[i] = make_pair(-1, INT_MAX);
	}

	cin >> n >> k;
	for (int i = 0; i < n + k - 1; ++i) {
		char op;
		cin >> op;
		int v;
		cin >> v;
		--v;
		if (op == 'S') {
			int u;
			cin >> u;
			--u;
			g[v].push_back({u, i});
			g[u].push_back({v, i});
		} else if (op == 'Q') {
			qtype[i] = 1;
			int u;
			cin >> u;
			--u;
			qp[u].push_back({v, i});
			//cout << u + 1 << ' ' << v + 1 << '\n';
		} else {
			qtype[i] = 2;
			qu[v].push_back(i);
			//cout << v + 1 << '\n';
		}
	}

	decompose(0, n);
	
	for (int i = 0; i < n + k - 1; ++i) {
		if (qtype[i] == 1) {
			cout << (ans[i] ? "yes" : "no") << '\n';
		} else if (qtype[i] == 2) {
			cout << ans[i] << '\n';
		}
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35900 KB Output is correct
2 Correct 59 ms 37472 KB Output is correct
3 Correct 47 ms 37316 KB Output is correct
4 Correct 58 ms 37652 KB Output is correct
5 Correct 53 ms 37452 KB Output is correct
6 Correct 65 ms 37252 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35900 KB Output is correct
2 Correct 59 ms 37472 KB Output is correct
3 Correct 47 ms 37316 KB Output is correct
4 Correct 58 ms 37652 KB Output is correct
5 Correct 53 ms 37452 KB Output is correct
6 Correct 65 ms 37252 KB Output is correct
7 Incorrect 40 ms 36548 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35912 KB Output is correct
2 Correct 163 ms 46504 KB Output is correct
3 Correct 180 ms 46520 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35912 KB Output is correct
2 Correct 163 ms 46504 KB Output is correct
3 Correct 180 ms 46520 KB Output is correct
4 Incorrect 40 ms 35908 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 35800 KB Output is correct
2 Correct 376 ms 56344 KB Output is correct
3 Correct 328 ms 56376 KB Output is correct
4 Correct 279 ms 56640 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 35800 KB Output is correct
2 Correct 376 ms 56344 KB Output is correct
3 Correct 328 ms 56376 KB Output is correct
4 Correct 279 ms 56640 KB Output is correct
5 Incorrect 53 ms 36524 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 35724 KB Output is correct
2 Correct 277 ms 48068 KB Output is correct
3 Correct 277 ms 47340 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 35724 KB Output is correct
2 Correct 277 ms 48068 KB Output is correct
3 Correct 277 ms 47340 KB Output is correct
4 Incorrect 44 ms 36576 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 35804 KB Output is correct
2 Correct 338 ms 56292 KB Output is correct
3 Correct 325 ms 56364 KB Output is correct
4 Correct 274 ms 56620 KB Output is correct
5 Correct 49 ms 36556 KB Output is correct
6 Correct 267 ms 48260 KB Output is correct
7 Correct 298 ms 47296 KB Output is correct
8 Correct 293 ms 47896 KB Output is correct
9 Correct 364 ms 48576 KB Output is correct
10 Correct 404 ms 52684 KB Output is correct
11 Correct 357 ms 51388 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 35804 KB Output is correct
2 Correct 338 ms 56292 KB Output is correct
3 Correct 325 ms 56364 KB Output is correct
4 Correct 274 ms 56620 KB Output is correct
5 Correct 49 ms 36556 KB Output is correct
6 Correct 267 ms 48260 KB Output is correct
7 Correct 298 ms 47296 KB Output is correct
8 Correct 293 ms 47896 KB Output is correct
9 Correct 364 ms 48576 KB Output is correct
10 Correct 404 ms 52684 KB Output is correct
11 Correct 357 ms 51388 KB Output is correct
12 Incorrect 38 ms 36524 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35820 KB Output is correct
2 Correct 49 ms 37572 KB Output is correct
3 Correct 48 ms 37288 KB Output is correct
4 Correct 53 ms 37676 KB Output is correct
5 Correct 69 ms 37444 KB Output is correct
6 Correct 49 ms 37312 KB Output is correct
7 Correct 37 ms 36676 KB Output is correct
8 Correct 170 ms 49128 KB Output is correct
9 Correct 163 ms 49132 KB Output is correct
10 Correct 38 ms 36456 KB Output is correct
11 Correct 405 ms 56408 KB Output is correct
12 Correct 317 ms 56336 KB Output is correct
13 Correct 265 ms 56572 KB Output is correct
14 Correct 38 ms 36548 KB Output is correct
15 Correct 270 ms 48056 KB Output is correct
16 Correct 323 ms 47400 KB Output is correct
17 Correct 266 ms 47812 KB Output is correct
18 Correct 290 ms 48520 KB Output is correct
19 Correct 425 ms 52420 KB Output is correct
20 Correct 371 ms 51360 KB Output is correct
21 Correct 178 ms 48612 KB Output is correct
22 Correct 227 ms 48332 KB Output is correct
23 Correct 243 ms 48040 KB Output is correct
24 Correct 233 ms 48200 KB Output is correct
25 Correct 347 ms 54420 KB Output is correct
26 Correct 277 ms 45888 KB Output is correct
27 Correct 242 ms 45668 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35820 KB Output is correct
2 Correct 49 ms 37572 KB Output is correct
3 Correct 48 ms 37288 KB Output is correct
4 Correct 53 ms 37676 KB Output is correct
5 Correct 69 ms 37444 KB Output is correct
6 Correct 49 ms 37312 KB Output is correct
7 Correct 37 ms 36676 KB Output is correct
8 Correct 170 ms 49128 KB Output is correct
9 Correct 163 ms 49132 KB Output is correct
10 Correct 38 ms 36456 KB Output is correct
11 Correct 405 ms 56408 KB Output is correct
12 Correct 317 ms 56336 KB Output is correct
13 Correct 265 ms 56572 KB Output is correct
14 Correct 38 ms 36548 KB Output is correct
15 Correct 270 ms 48056 KB Output is correct
16 Correct 323 ms 47400 KB Output is correct
17 Correct 266 ms 47812 KB Output is correct
18 Correct 290 ms 48520 KB Output is correct
19 Correct 425 ms 52420 KB Output is correct
20 Correct 371 ms 51360 KB Output is correct
21 Correct 178 ms 48612 KB Output is correct
22 Correct 227 ms 48332 KB Output is correct
23 Correct 243 ms 48040 KB Output is correct
24 Correct 233 ms 48200 KB Output is correct
25 Correct 347 ms 54420 KB Output is correct
26 Correct 277 ms 45888 KB Output is correct
27 Correct 242 ms 45668 KB Output is correct
28 Incorrect 44 ms 36804 KB Extra information in the output file
29 Halted 0 ms 0 KB -