oj.uz

Submission #528459

# Submission time Handle Problem Language Result Execution time Memory
528459 2022-02-20T10:35:17 Z iliaM Inside information (BOI21_servers) C++17
50 / 100
 389 ms 53852 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;
	int cc = 0;
	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') {
			++cc;
			qtype[i] = 1;
			int u;
			cin >> u;
			--u;
			qp[u].push_back({v, i});
			//cout << u + 1 << ' ' << v + 1 << '\n';
		} else {
			++cc;
			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) {
			--cc;
			if (cc < 0) {
				assert(false);
			}
			cout << (ans[i] ? "yes" : "no") << '\n';
		} else if (qtype[i] == 2) {
			--cc;
			if (cc < 0) {
				assert(false);
			}
			cout << ans[i] << '\n';
		}
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 36040 KB Output is correct
2 Correct 53 ms 36552 KB Output is correct
3 Correct 45 ms 36292 KB Output is correct
4 Correct 50 ms 36676 KB Output is correct
5 Correct 49 ms 36364 KB Output is correct
6 Correct 45 ms 36356 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 36040 KB Output is correct
2 Correct 53 ms 36552 KB Output is correct
3 Correct 45 ms 36292 KB Output is correct
4 Correct 50 ms 36676 KB Output is correct
5 Correct 49 ms 36364 KB Output is correct
6 Correct 45 ms 36356 KB Output is correct
7 Incorrect 38 ms 36056 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 39 ms 36140 KB Output is correct
2 Correct 152 ms 46752 KB Output is correct
3 Correct 143 ms 46816 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 36140 KB Output is correct
2 Correct 152 ms 46752 KB Output is correct
3 Correct 143 ms 46816 KB Output is correct
4 Incorrect 37 ms 36096 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 37 ms 36020 KB Output is correct
2 Correct 320 ms 53464 KB Output is correct
3 Correct 302 ms 53436 KB Output is correct
4 Correct 259 ms 53816 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 36020 KB Output is correct
2 Correct 320 ms 53464 KB Output is correct
3 Correct 302 ms 53436 KB Output is correct
4 Correct 259 ms 53816 KB Output is correct
5 Incorrect 38 ms 36036 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 37 ms 36024 KB Output is correct
2 Correct 273 ms 45204 KB Output is correct
3 Correct 298 ms 44372 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 36024 KB Output is correct
2 Correct 273 ms 45204 KB Output is correct
3 Correct 298 ms 44372 KB Output is correct
4 Incorrect 38 ms 36048 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 37 ms 36064 KB Output is correct
2 Correct 310 ms 53424 KB Output is correct
3 Correct 312 ms 53432 KB Output is correct
4 Correct 271 ms 53852 KB Output is correct
5 Correct 38 ms 35960 KB Output is correct
6 Correct 259 ms 45200 KB Output is correct
7 Correct 271 ms 44512 KB Output is correct
8 Correct 266 ms 44968 KB Output is correct
9 Correct 285 ms 45696 KB Output is correct
10 Correct 389 ms 49504 KB Output is correct
11 Correct 336 ms 48380 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 36064 KB Output is correct
2 Correct 310 ms 53424 KB Output is correct
3 Correct 312 ms 53432 KB Output is correct
4 Correct 271 ms 53852 KB Output is correct
5 Correct 38 ms 35960 KB Output is correct
6 Correct 259 ms 45200 KB Output is correct
7 Correct 271 ms 44512 KB Output is correct
8 Correct 266 ms 44968 KB Output is correct
9 Correct 285 ms 45696 KB Output is correct
10 Correct 389 ms 49504 KB Output is correct
11 Correct 336 ms 48380 KB Output is correct
12 Incorrect 41 ms 36036 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 36092 KB Output is correct
2 Correct 52 ms 36528 KB Output is correct
3 Correct 46 ms 36292 KB Output is correct
4 Correct 50 ms 36608 KB Output is correct
5 Correct 50 ms 36420 KB Output is correct
6 Correct 49 ms 36292 KB Output is correct
7 Correct 42 ms 36164 KB Output is correct
8 Correct 154 ms 46608 KB Output is correct
9 Correct 154 ms 46664 KB Output is correct
10 Correct 39 ms 36164 KB Output is correct
11 Correct 303 ms 53432 KB Output is correct
12 Correct 312 ms 53364 KB Output is correct
13 Correct 256 ms 53724 KB Output is correct
14 Correct 37 ms 36036 KB Output is correct
15 Correct 253 ms 45148 KB Output is correct
16 Correct 278 ms 44380 KB Output is correct
17 Correct 255 ms 45008 KB Output is correct
18 Correct 286 ms 45728 KB Output is correct
19 Correct 360 ms 49452 KB Output is correct
20 Correct 359 ms 48404 KB Output is correct
21 Correct 174 ms 45612 KB Output is correct
22 Correct 182 ms 45256 KB Output is correct
23 Correct 218 ms 45260 KB Output is correct
24 Correct 231 ms 45248 KB Output is correct
25 Correct 360 ms 51476 KB Output is correct
26 Correct 288 ms 42932 KB Output is correct
27 Correct 255 ms 42596 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 36092 KB Output is correct
2 Correct 52 ms 36528 KB Output is correct
3 Correct 46 ms 36292 KB Output is correct
4 Correct 50 ms 36608 KB Output is correct
5 Correct 50 ms 36420 KB Output is correct
6 Correct 49 ms 36292 KB Output is correct
7 Correct 42 ms 36164 KB Output is correct
8 Correct 154 ms 46608 KB Output is correct
9 Correct 154 ms 46664 KB Output is correct
10 Correct 39 ms 36164 KB Output is correct
11 Correct 303 ms 53432 KB Output is correct
12 Correct 312 ms 53364 KB Output is correct
13 Correct 256 ms 53724 KB Output is correct
14 Correct 37 ms 36036 KB Output is correct
15 Correct 253 ms 45148 KB Output is correct
16 Correct 278 ms 44380 KB Output is correct
17 Correct 255 ms 45008 KB Output is correct
18 Correct 286 ms 45728 KB Output is correct
19 Correct 360 ms 49452 KB Output is correct
20 Correct 359 ms 48404 KB Output is correct
21 Correct 174 ms 45612 KB Output is correct
22 Correct 182 ms 45256 KB Output is correct
23 Correct 218 ms 45260 KB Output is correct
24 Correct 231 ms 45248 KB Output is correct
25 Correct 360 ms 51476 KB Output is correct
26 Correct 288 ms 42932 KB Output is correct
27 Correct 255 ms 42596 KB Output is correct
28 Incorrect 39 ms 36172 KB Extra information in the output file
29 Halted 0 ms 0 KB -