Submission #528291

#	Time	Username	Problem	Language	Result	Execution time	Memory
528291		iliaM	Inside information (BOI21_servers)	C++17	0 / 100	39 ms	28048 KiB

servers

#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;
pair<int, int> tmp[N]; 
vector<pair<int, pair<int, int>>> pairs;
vector<int> verts;
bool mark[N];
int sz[N];
vector<pair<int, int>> g[N];
bool used[N];
long long ans[N];
int parent[N];

int centroid(int v, int p, int m) {
	tmp[v] = make_pair(INT_MAX, INT_MAX);
	verts.push_back(v);
	mark[v] = true;

	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];
		}
	}
	//cerr << cool << '\n';
	return cool && m - sz[v] <= m / 2 ? v : ~ret;
}


void dfs(int v, int p, int fe, int f, int s) {
	//cerr << "DFSING: " << v << '\n';
	sz[v] = 1;
	parent[v] = fe;
	if (~f) {
		for (auto &query : qu[v]) {
			up.push_back({fe, query});
		}
		for (auto &query : qp[v]) {
			pairs.push_back({query.first, {fe, query.second}});
		}
	}
	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];
		}
	}
	//cerr << "UNDFSING: " << v << ' ' << sz[v] << '\n';
}

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.first, -1);
	}
}

void decompose(int v, int m) {
	verts.clear();
	int cent = centroid(v, -1, m);
	
	//cerr << v << ' ' << cent << ' ' << m << '\n';

	up.clear();
	down.clear();
	pairs.clear();

	/*for (int i = 0; i < n; ++i) {
		cout << sz[i] << ' ';
	}
	cout << '\n';*/
	for (auto &e : g[cent]) {
		int u = e.first, w = e.second;
		if (!used[u]) {
			//cerr << u << '\n';
			dfs(u, cent, w, w, w);
		}
	}
	/*for (int i = 0; i < n; ++i) {
		cout << sz[i] << ' ';
	}
	cout << '\n';*/
	
	// calc for pairs in subtrees
	sort(down.begin(), down.end());
	solve();
	for (auto &pr : pairs) {
		int x = pr.first;
		if (parent[x] == pr.second.first) {
			continue;
		}
		if (x == cent) {
			ans[pr.second.second] = 1;
		} else if (mark[x]) {
			bool ok = pr.second.first < tmp[x].first && tmp[x].second < pr.second.second;
			ans[pr.second.second] = ok;
		}
	}

	// calc for pairs from centroid
	for (auto &query : qp[cent]) {
		if (mark[query.first]) {
			ans[query.second] = query.first == cent || tmp[query.first].second < query.second;
		}
	}
	for (auto &query : qu[cent]) {
		ans[query] += 1 + down.size();
	}

	for (auto &v : verts) {
		mark[v] = false;
	}
	used[cent] = true;
	for (auto &e : g[cent]) {
		int u = e.first;
		if (!used[u]) {
			//cerr << "DOING: " << u << ' ' << sz[u] << '\n';
			decompose(u, sz[u]);
		}
	}
}

int qtype[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
		
	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
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5