oj.uz

Submission #528499

# Submission time Handle Problem Language Result Execution time Memory
528499 2022-02-20T11:52:17 Z koioi.org-koosaga Inside information (BOI21_servers) C++17
80 / 100
 3500 ms 64808 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
using pi = pair<int, int>;
const int MAXN = 120005;

vector<pi> gph[MAXN];

namespace CD{
	int sz[MAXN], msz[MAXN], vis[MAXN];
	vector<int> dfn;
	void dfs(int x, int p = -1){
		sz[x] = 1;
		msz[x] = 0;
		dfn.push_back(x);
		for(auto &[_, y] : gph[x]){
			if(y != p && !vis[y]){
				dfs(y, x);
				sz[x] += sz[y];
				msz[x] = max(msz[x], sz[y]);
			}
		}
	}
	int get_center(int x){
		dfn.clear();
		dfs(x);
		pi ret(1e9, -1);
		for(auto &v : dfn){
			int val = max(msz[v], sz(dfn) - sz[v]);
			ret = min(ret, pi(val, v));
		}
		return ret.second;
	}
	pi good[17][MAXN];
	pi can[17][MAXN];
	void dfs2(int x, int l, int r, int p, vector<pi> &strg, int depth){
		can[depth][x] = pi(l, r);
		strg.emplace_back(l, r);
		for(auto &[c, y] : gph[x]){
			if(!vis[y] && y != p && r < c) dfs2(y, l, c, x, strg, depth);
		}
	}
	void dfs3(int x, int l, int r, int p, int depth){
		good[depth][x].second = 1;
		good[depth][x].first = l;
		for(auto &[c, y] : gph[x]){
			if(!vis[y] && y != p && r > c) dfs3(y, l, c, x, depth);
		}
	}
	int par[MAXN], dep[MAXN];
	vector<pi> ds[MAXN];
	void init(int n){
		memset(can, 0x3f, sizeof(can));
		queue<pi> que;
		que.push(pi(1, -1));
		while(sz(que)){
			int x = que.front().first;
			int p = que.front().second;
			que.pop();
			x = get_center(x);
			vis[x] = 1;
			par[x] = p;
			if(~p) dep[x] = dep[p] + 1;
			good[dep[x]][x] = pi(-1e9, 1);
			can[dep[x]][x] = pi(1e9, -1e9);
			for(auto &[c, y] : gph[x]){
				if(vis[y]) continue;
				que.emplace(y, x);
				dfs2(y, c, c, -1, ds[x], dep[x]);
				dfs3(y, c, c, -1, dep[x]);
			}
		}
	}
	int query(int v, int hi){
		int ans = 0;
		for(int w = v; ~w; w = par[w]){
			if(!good[dep[w]][v].second) continue;
			if(good[dep[w]][v].first > hi) continue;
			int lo = good[dep[w]][v].first + 1;
			ans++;
			for(auto &[s, e] : ds[w]){
				if(lo <= s && e <= hi) ans++; 
			}
		}
		return ans;
	}
	int lca(int x, int y){
		if(dep[x] > dep[y]) swap(x, y);
		while(dep[x] < dep[y]) y = par[y];
		while(x != y){
			x = par[x], y = par[y];
		}
		return x;
	}
	bool reach(int u, int v, int d){
		int l = lca(u, v);
		if(!good[dep[l]][u].second) return 0;
		if(can[dep[l]][v].second > d) return 0;
		if(good[dep[l]][u].first > d) return 0;
		if(good[dep[l]][u].first > can[dep[l]][v].first) return 0;
		return 1;
	}
};

struct query{
	int t, u, v, lim, idx;
};

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, q;
	cin >> n >> q;
	int c = 0;
	vector<query> qry;
	for(int i = 0; i < n+q-1; i++){
		string s; cin >> s;
		if(s == "S"){
			int u, v; cin >> u >> v;
			c++;
			gph[u].emplace_back(c, v);
			gph[v].emplace_back(c, u);
		}
		else if(s == "Q"){
			int u, v; cin >> u >> v;
			int sq = sz(qry);
			qry.push_back({1, v, u, c, sq});
		}
		else{
			int sq = sz(qry);
			int u; cin >> u;
			qry.push_back({2, u, -1, c, sq});
		}
	}
	CD::init(n);
	for(auto &i : qry){
		if(i.t == 1) cout << (CD::reach(i.u, i.v, i.lim) ? "yes" : "no") << "\n";
		else cout << CD::query(i.u, i.lim) << "\n";
	}
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 25260 KB Output is correct
2 Correct 49 ms 25576 KB Output is correct
3 Correct 45 ms 25400 KB Output is correct
4 Correct 50 ms 25768 KB Output is correct
5 Correct 52 ms 25860 KB Output is correct
6 Correct 56 ms 25308 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 25260 KB Output is correct
2 Correct 49 ms 25576 KB Output is correct
3 Correct 45 ms 25400 KB Output is correct
4 Correct 50 ms 25768 KB Output is correct
5 Correct 52 ms 25860 KB Output is correct
6 Correct 56 ms 25308 KB Output is correct
7 Correct 56 ms 25012 KB Output is correct
8 Correct 53 ms 26404 KB Output is correct
9 Correct 113 ms 26304 KB Output is correct
10 Correct 52 ms 26464 KB Output is correct
11 Correct 58 ms 26576 KB Output is correct
12 Correct 198 ms 26176 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 25264 KB Output is correct
2 Correct 137 ms 36560 KB Output is correct
3 Correct 105 ms 36544 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 25264 KB Output is correct
2 Correct 137 ms 36560 KB Output is correct
3 Correct 105 ms 36544 KB Output is correct
4 Correct 40 ms 24992 KB Output is correct
5 Correct 1360 ms 38048 KB Output is correct
6 Execution timed out 3536 ms 37828 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 25264 KB Output is correct
2 Correct 291 ms 53632 KB Output is correct
3 Correct 239 ms 53700 KB Output is correct
4 Correct 170 ms 63848 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 25264 KB Output is correct
2 Correct 291 ms 53632 KB Output is correct
3 Correct 239 ms 53700 KB Output is correct
4 Correct 170 ms 63848 KB Output is correct
5 Correct 58 ms 25056 KB Output is correct
6 Correct 255 ms 54772 KB Output is correct
7 Correct 1343 ms 64688 KB Output is correct
8 Correct 255 ms 54628 KB Output is correct
9 Correct 296 ms 54632 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 25264 KB Output is correct
2 Correct 171 ms 49768 KB Output is correct
3 Correct 261 ms 42272 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 25264 KB Output is correct
2 Correct 171 ms 49768 KB Output is correct
3 Correct 261 ms 42272 KB Output is correct
4 Correct 42 ms 25024 KB Output is correct
5 Correct 1156 ms 50996 KB Output is correct
6 Correct 243 ms 43380 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 25320 KB Output is correct
2 Correct 249 ms 53668 KB Output is correct
3 Correct 286 ms 53668 KB Output is correct
4 Correct 167 ms 63824 KB Output is correct
5 Correct 41 ms 25028 KB Output is correct
6 Correct 161 ms 49900 KB Output is correct
7 Correct 263 ms 42376 KB Output is correct
8 Correct 264 ms 47784 KB Output is correct
9 Correct 264 ms 47356 KB Output is correct
10 Correct 344 ms 58660 KB Output is correct
11 Correct 317 ms 58000 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 25320 KB Output is correct
2 Correct 249 ms 53668 KB Output is correct
3 Correct 286 ms 53668 KB Output is correct
4 Correct 167 ms 63824 KB Output is correct
5 Correct 41 ms 25028 KB Output is correct
6 Correct 161 ms 49900 KB Output is correct
7 Correct 263 ms 42376 KB Output is correct
8 Correct 264 ms 47784 KB Output is correct
9 Correct 264 ms 47356 KB Output is correct
10 Correct 344 ms 58660 KB Output is correct
11 Correct 317 ms 58000 KB Output is correct
12 Correct 42 ms 25008 KB Output is correct
13 Correct 258 ms 54744 KB Output is correct
14 Correct 1411 ms 64808 KB Output is correct
15 Correct 244 ms 54628 KB Output is correct
16 Correct 351 ms 54684 KB Output is correct
17 Correct 45 ms 25652 KB Output is correct
18 Correct 1146 ms 51024 KB Output is correct
19 Correct 282 ms 43344 KB Output is correct
20 Correct 276 ms 48972 KB Output is correct
21 Correct 286 ms 48960 KB Output is correct
22 Correct 667 ms 58968 KB Output is correct
23 Correct 1346 ms 62800 KB Output is correct
24 Correct 723 ms 62224 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 25280 KB Output is correct
2 Correct 49 ms 25544 KB Output is correct
3 Correct 48 ms 25536 KB Output is correct
4 Correct 56 ms 25740 KB Output is correct
5 Correct 50 ms 25800 KB Output is correct
6 Correct 44 ms 25332 KB Output is correct
7 Correct 40 ms 25040 KB Output is correct
8 Correct 109 ms 36504 KB Output is correct
9 Correct 111 ms 36488 KB Output is correct
10 Correct 43 ms 25012 KB Output is correct
11 Correct 224 ms 53664 KB Output is correct
12 Correct 246 ms 53736 KB Output is correct
13 Correct 167 ms 63780 KB Output is correct
14 Correct 40 ms 24996 KB Output is correct
15 Correct 159 ms 49788 KB Output is correct
16 Correct 248 ms 42424 KB Output is correct
17 Correct 278 ms 47720 KB Output is correct
18 Correct 282 ms 47180 KB Output is correct
19 Correct 370 ms 58780 KB Output is correct
20 Correct 303 ms 57932 KB Output is correct
21 Correct 133 ms 38004 KB Output is correct
22 Correct 132 ms 37676 KB Output is correct
23 Correct 170 ms 44872 KB Output is correct
24 Correct 208 ms 44252 KB Output is correct
25 Correct 293 ms 51984 KB Output is correct
26 Correct 289 ms 47444 KB Output is correct
27 Correct 331 ms 47464 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 25280 KB Output is correct
2 Correct 49 ms 25544 KB Output is correct
3 Correct 48 ms 25536 KB Output is correct
4 Correct 56 ms 25740 KB Output is correct
5 Correct 50 ms 25800 KB Output is correct
6 Correct 44 ms 25332 KB Output is correct
7 Correct 40 ms 25040 KB Output is correct
8 Correct 109 ms 36504 KB Output is correct
9 Correct 111 ms 36488 KB Output is correct
10 Correct 43 ms 25012 KB Output is correct
11 Correct 224 ms 53664 KB Output is correct
12 Correct 246 ms 53736 KB Output is correct
13 Correct 167 ms 63780 KB Output is correct
14 Correct 40 ms 24996 KB Output is correct
15 Correct 159 ms 49788 KB Output is correct
16 Correct 248 ms 42424 KB Output is correct
17 Correct 278 ms 47720 KB Output is correct
18 Correct 282 ms 47180 KB Output is correct
19 Correct 370 ms 58780 KB Output is correct
20 Correct 303 ms 57932 KB Output is correct
21 Correct 133 ms 38004 KB Output is correct
22 Correct 132 ms 37676 KB Output is correct
23 Correct 170 ms 44872 KB Output is correct
24 Correct 208 ms 44252 KB Output is correct
25 Correct 293 ms 51984 KB Output is correct
26 Correct 289 ms 47444 KB Output is correct
27 Correct 331 ms 47464 KB Output is correct
28 Correct 43 ms 24964 KB Output is correct
29 Correct 52 ms 26388 KB Output is correct
30 Correct 87 ms 26356 KB Output is correct
31 Correct 65 ms 26556 KB Output is correct
32 Correct 55 ms 26616 KB Output is correct
33 Correct 192 ms 26180 KB Output is correct
34 Correct 43 ms 25576 KB Output is correct
35 Correct 1393 ms 37904 KB Output is correct
36 Execution timed out 3560 ms 37644 KB Time limit exceeded
37 Halted 0 ms 0 KB -