oj.uz

Submission #528302

# Submission time Handle Problem Language Result Execution time Memory
528302 2022-02-19T20:44:25 Z iliaM Inside information (BOI21_servers) C++17
2.5 / 100
 183 ms 40296 KB 
#include <bits/stdc++.h>
using namespace std;
#define cerr cerr << "DEBUG "

constexpr int N = 24e4 + 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);
	}
	for (auto &e : g[v]) {
		int u = e.first, w = e.second;
		if (u != p && !used[u]) {
			dfs(u, v, fe, w < f ? w : -1, w > s ? w : -1);
			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();

	for (auto &e : g[cent]) {
		int u = e.first, w = e.second;
		if (!used[u]) {
			dfs(u, cent, w, w, w);
		}
	}
	
	// calc for pairs in subtrees
	sort(down.begin(), down.end());
	solve();

	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 &v : verts) {
		mark[v] = -1;
		tmp[v] = make_pair(-1, INT_MAX);
		has[v] = 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});
		} else {
			qtype[i] = 2;
			qu[v].push_back(i);
		}
	}

	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
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 29640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 29640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 29676 KB Output is correct
2 Correct 183 ms 40296 KB Output is correct
3 Correct 174 ms 40208 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 29676 KB Output is correct
2 Correct 183 ms 40296 KB Output is correct
3 Correct 174 ms 40208 KB Output is correct
4 Incorrect 34 ms 29820 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 29468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 29468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 29484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 29484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 29476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 29476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 29560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 29560 KB Output isn't correct
2 Halted 0 ms 0 KB -