Submission #1093607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093607		CDuong	Inside information (BOI21_servers)	C++17	100 / 100	306 ms	32128 KiB

servers

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>
 
using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;
 
void Hollwo_Pelw();
 
signed main(){
#ifndef hollwo_pelw_local
	if (fopen("servers.inp", "r")){
		freopen("servers.inp", "r", stdin);
		freopen("servers.out", "w", stdout);
	}
#else
	auto start = chrono::steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = chrono::steady_clock::now();
	cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}
 
#define for_cen(v, w, u) for (auto [v, w] : adj[u]) if (!mark[v])
 
const int N = 1.2e5 + 5, Q = N << 1;
 
vector<pair<int, int>> query_q[N];
vector<int> query_c[N];
vector<pair<int, int>> adj[N];
 
int n, q, siz[N], mark[N];
 
int find_sz(int u, int p) {
	siz[u] = 1;
	for_cen(v, w, u) if (v != p)
		siz[u] += find_sz(v, u);
	return siz[u];
}
 
int find_cen(int u, int p, const int &tot) {
	for_cen(v, w, u) if (v != p)
		if (siz[v] > tot / 2) return find_cen(v, u, tot);
	return u;
}
 
struct fenwick_tree {
	int bit[Q], ver[Q], vercnt;
 
	inline void clear() { vercnt ++; }
 
	inline void add(int p, int v) {
		for (; p < Q; p += p & -p) {
			if (ver[p] ^ vercnt)
				ver[p] = vercnt, bit[p] = 0;
			bit[p] += v;
		}
	}
 
	inline int query(int p) {
		int r = 0;
		for (; p > 0; p -= p & -p) {
			if (ver[p] ^ vercnt)
				ver[p] = vercnt, bit[p] = 0;
			r += bit[p];
		}
		return r;
	}
 
} bit;
 
vector<int> inQ, outQ, allinQ;
 
int res[Q], curin[N], curout[N];
 
void dfs_in(int u, int p, int cur) {
	inQ.push_back(u);
 
	for_cen(v, w, u) if (v != p) {
		if (w < cur)
			dfs_in(v, u, w);
	}
}
 
void dfs_out(int u, int p, int cur) {
	outQ.push_back(u);
	
	bit.add(cur, 1);
	curout[u] = cur;
 
	for_cen(v, w, u) if (v != p) {
		if (w > cur)
			dfs_out(v, u, w);
	}
}
 
void centroid_decomp(int r) {
	int tot = find_sz(r, -1);
	r = find_cen(r, -1, tot);
 
	sort(adj[r].begin(), adj[r].end(), [&](const pair<int, int> &a, const pair<int, int> &b){
		return a.second > b.second;
	});
 
	bit.clear();
 
	curin[r] = 0;
 
	for_cen(v, w, r) {
		inQ.clear();
		outQ.clear();
		dfs_in(v, r, w);
 
		for (auto u : inQ) {
			for (auto i : query_c[u]) if (i >= w)
				res[i] += 1 + bit.query(i);
			curin[u] = w;
		}
 
		dfs_out(v, r, w);
	}
 
	for (auto i : query_c[r])
		res[i] += 1 + bit.query(i);
 
	reverse(adj[r].begin(), adj[r].end());
 
	bit.clear();
	
	allinQ.push_back(r);
 
	for_cen(v, w, r) {
		inQ.clear();
		outQ.clear();
		dfs_in(v, r, w);
 
		for (auto u : inQ) {
			allinQ.push_back(u);
		}
 
		dfs_out(v, r, w);
 
		for (auto u : outQ) {
			for (auto [i, v] : query_q[u])
				if (curin[v] != -1 && curin[v] < w && i > curout[u]) {
					res[i] = 1;
				}
		}
	}
 
	for (auto [i, v] : query_q[r])
		if (curin[v] != -1 && i > curin[v]) {
			res[i] = 1;
		}
 
	for (auto u : allinQ)
		curin[u] = -1;
 
	allinQ.clear();
 
	mark[r] = 1;
	for_cen(v, w, r)
		centroid_decomp(v);
}
 
char t[Q];
 
void Hollwo_Pelw(){
	cin >> n >> q, q += n - 1;
	for (int i = 1, u, v; i <= q; i++) {
		cin >> t[i];
		if (t[i] == 'S') {
			cin >> u >> v;
			adj[u].emplace_back(v, i);
			adj[v].emplace_back(u, i);
		}
		if (t[i] == 'Q') {
			cin >> u >> v;
			query_q[u].emplace_back(i, v);
		}
		if (t[i] == 'C') {
			cin >> u;
			query_c[u].push_back(i);
		}
	}
 
	memset(curin, -1, sizeof curin);
 
	centroid_decomp(1);
 
	for (int i = 1; i <= q; i++) {
		if (t[i] == 'Q')
			cout << (res[i] ? "yes\n" : "no\n");
		if (t[i] == 'C')
			cout << res[i] << '\n';
	}
 
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:15:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   freopen("servers.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:16:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   freopen("servers.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5