oj.uz

Submission #534435

# Submission time Handle Problem Language Result Execution time Memory
534435 2022-03-08T07:07:47 Z hollwo_pelw Inside information (BOI21_servers) C++17
52.5 / 100
 285 ms 28520 KB 
#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);

	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) - bit.query(w);
			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) {
			for (auto i : query_c[u]) if (i >= w)
				res[i] += bit.query(i) - bit.query(w);
			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

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

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12364 KB Output is correct
2 Correct 36 ms 12792 KB Output is correct
3 Correct 32 ms 12800 KB Output is correct
4 Correct 36 ms 12888 KB Output is correct
5 Correct 41 ms 12220 KB Output is correct
6 Correct 34 ms 12416 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12364 KB Output is correct
2 Correct 36 ms 12792 KB Output is correct
3 Correct 32 ms 12800 KB Output is correct
4 Correct 36 ms 12888 KB Output is correct
5 Correct 41 ms 12220 KB Output is correct
6 Correct 34 ms 12416 KB Output is correct
7 Correct 29 ms 12436 KB Output is correct
8 Incorrect 47 ms 13680 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12496 KB Output is correct
2 Correct 154 ms 21928 KB Output is correct
3 Correct 150 ms 22028 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12496 KB Output is correct
2 Correct 154 ms 21928 KB Output is correct
3 Correct 150 ms 22028 KB Output is correct
4 Correct 25 ms 12492 KB Output is correct
5 Correct 144 ms 24544 KB Output is correct
6 Correct 102 ms 22116 KB Output is correct
7 Correct 115 ms 22300 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12404 KB Output is correct
2 Correct 239 ms 27720 KB Output is correct
3 Correct 232 ms 27744 KB Output is correct
4 Correct 210 ms 28352 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12404 KB Output is correct
2 Correct 239 ms 27720 KB Output is correct
3 Correct 232 ms 27744 KB Output is correct
4 Correct 210 ms 28352 KB Output is correct
5 Incorrect 26 ms 12492 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 23 ms 12364 KB Output is correct
2 Correct 211 ms 21616 KB Output is correct
3 Correct 178 ms 21048 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12364 KB Output is correct
2 Correct 211 ms 21616 KB Output is correct
3 Correct 178 ms 21048 KB Output is correct
4 Incorrect 24 ms 12492 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 24 ms 12364 KB Output is correct
2 Correct 232 ms 27740 KB Output is correct
3 Correct 225 ms 27808 KB Output is correct
4 Correct 207 ms 28416 KB Output is correct
5 Correct 23 ms 12364 KB Output is correct
6 Correct 202 ms 21676 KB Output is correct
7 Correct 184 ms 20980 KB Output is correct
8 Correct 201 ms 20872 KB Output is correct
9 Correct 205 ms 21872 KB Output is correct
10 Correct 285 ms 25612 KB Output is correct
11 Correct 274 ms 23836 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12364 KB Output is correct
2 Correct 232 ms 27740 KB Output is correct
3 Correct 225 ms 27808 KB Output is correct
4 Correct 207 ms 28416 KB Output is correct
5 Correct 23 ms 12364 KB Output is correct
6 Correct 202 ms 21676 KB Output is correct
7 Correct 184 ms 20980 KB Output is correct
8 Correct 201 ms 20872 KB Output is correct
9 Correct 205 ms 21872 KB Output is correct
10 Correct 285 ms 25612 KB Output is correct
11 Correct 274 ms 23836 KB Output is correct
12 Incorrect 24 ms 12508 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 26 ms 12348 KB Output is correct
2 Correct 35 ms 12728 KB Output is correct
3 Correct 38 ms 12804 KB Output is correct
4 Correct 36 ms 12996 KB Output is correct
5 Correct 32 ms 12196 KB Output is correct
6 Correct 37 ms 12432 KB Output is correct
7 Correct 33 ms 12492 KB Output is correct
8 Correct 160 ms 22044 KB Output is correct
9 Correct 147 ms 21956 KB Output is correct
10 Correct 32 ms 12364 KB Output is correct
11 Correct 237 ms 27716 KB Output is correct
12 Correct 223 ms 27768 KB Output is correct
13 Correct 214 ms 28520 KB Output is correct
14 Correct 24 ms 12432 KB Output is correct
15 Correct 195 ms 21592 KB Output is correct
16 Correct 185 ms 21060 KB Output is correct
17 Correct 197 ms 20776 KB Output is correct
18 Correct 209 ms 21816 KB Output is correct
19 Correct 282 ms 25620 KB Output is correct
20 Correct 273 ms 23764 KB Output is correct
21 Correct 165 ms 22044 KB Output is correct
22 Correct 174 ms 21736 KB Output is correct
23 Correct 183 ms 21480 KB Output is correct
24 Correct 175 ms 21568 KB Output is correct
25 Correct 254 ms 25184 KB Output is correct
26 Correct 267 ms 20412 KB Output is correct
27 Correct 253 ms 20432 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12348 KB Output is correct
2 Correct 35 ms 12728 KB Output is correct
3 Correct 38 ms 12804 KB Output is correct
4 Correct 36 ms 12996 KB Output is correct
5 Correct 32 ms 12196 KB Output is correct
6 Correct 37 ms 12432 KB Output is correct
7 Correct 33 ms 12492 KB Output is correct
8 Correct 160 ms 22044 KB Output is correct
9 Correct 147 ms 21956 KB Output is correct
10 Correct 32 ms 12364 KB Output is correct
11 Correct 237 ms 27716 KB Output is correct
12 Correct 223 ms 27768 KB Output is correct
13 Correct 214 ms 28520 KB Output is correct
14 Correct 24 ms 12432 KB Output is correct
15 Correct 195 ms 21592 KB Output is correct
16 Correct 185 ms 21060 KB Output is correct
17 Correct 197 ms 20776 KB Output is correct
18 Correct 209 ms 21816 KB Output is correct
19 Correct 282 ms 25620 KB Output is correct
20 Correct 273 ms 23764 KB Output is correct
21 Correct 165 ms 22044 KB Output is correct
22 Correct 174 ms 21736 KB Output is correct
23 Correct 183 ms 21480 KB Output is correct
24 Correct 175 ms 21568 KB Output is correct
25 Correct 254 ms 25184 KB Output is correct
26 Correct 267 ms 20412 KB Output is correct
27 Correct 253 ms 20432 KB Output is correct
28 Correct 26 ms 12492 KB Output is correct
29 Incorrect 45 ms 13672 KB Extra information in the output file
30 Halted 0 ms 0 KB -