oj.uz

Submission #528498

# Submission time Handle Problem Language Result Execution time Memory
528498 2022-02-20T11:51:02 Z koioi.org-koosaga Inside information (BOI21_servers) C++17
50 / 100
 314 ms 66300 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;
			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 44 ms 25260 KB Output is correct
2 Correct 50 ms 26640 KB Output is correct
3 Correct 47 ms 26572 KB Output is correct
4 Correct 56 ms 26932 KB Output is correct
5 Correct 49 ms 26972 KB Output is correct
6 Correct 42 ms 26476 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 25260 KB Output is correct
2 Correct 50 ms 26640 KB Output is correct
3 Correct 47 ms 26572 KB Output is correct
4 Correct 56 ms 26932 KB Output is correct
5 Correct 49 ms 26972 KB Output is correct
6 Correct 42 ms 26476 KB Output is correct
7 Incorrect 41 ms 25572 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 25292 KB Output is correct
2 Correct 106 ms 39092 KB Output is correct
3 Correct 107 ms 39080 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 25292 KB Output is correct
2 Correct 106 ms 39092 KB Output is correct
3 Correct 107 ms 39080 KB Output is correct
4 Incorrect 39 ms 25660 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 25280 KB Output is correct
2 Correct 245 ms 56180 KB Output is correct
3 Correct 241 ms 56016 KB Output is correct
4 Correct 166 ms 66256 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 25280 KB Output is correct
2 Correct 245 ms 56180 KB Output is correct
3 Correct 241 ms 56016 KB Output is correct
4 Correct 166 ms 66256 KB Output is correct
5 Incorrect 39 ms 25664 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 41 ms 25264 KB Output is correct
2 Correct 158 ms 52156 KB Output is correct
3 Correct 219 ms 44636 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 25264 KB Output is correct
2 Correct 158 ms 52156 KB Output is correct
3 Correct 219 ms 44636 KB Output is correct
4 Incorrect 40 ms 25648 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 44 ms 25260 KB Output is correct
2 Correct 242 ms 56216 KB Output is correct
3 Correct 225 ms 56056 KB Output is correct
4 Correct 172 ms 66300 KB Output is correct
5 Correct 39 ms 25692 KB Output is correct
6 Correct 159 ms 52192 KB Output is correct
7 Correct 211 ms 44640 KB Output is correct
8 Correct 248 ms 50164 KB Output is correct
9 Correct 271 ms 49620 KB Output is correct
10 Correct 306 ms 60972 KB Output is correct
11 Correct 314 ms 60468 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 25260 KB Output is correct
2 Correct 242 ms 56216 KB Output is correct
3 Correct 225 ms 56056 KB Output is correct
4 Correct 172 ms 66300 KB Output is correct
5 Correct 39 ms 25692 KB Output is correct
6 Correct 159 ms 52192 KB Output is correct
7 Correct 211 ms 44640 KB Output is correct
8 Correct 248 ms 50164 KB Output is correct
9 Correct 271 ms 49620 KB Output is correct
10 Correct 306 ms 60972 KB Output is correct
11 Correct 314 ms 60468 KB Output is correct
12 Incorrect 40 ms 25652 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 40 ms 25260 KB Output is correct
2 Correct 47 ms 26700 KB Output is correct
3 Correct 44 ms 26588 KB Output is correct
4 Correct 58 ms 26988 KB Output is correct
5 Correct 50 ms 27004 KB Output is correct
6 Correct 46 ms 26424 KB Output is correct
7 Correct 37 ms 25652 KB Output is correct
8 Correct 105 ms 39128 KB Output is correct
9 Correct 112 ms 39092 KB Output is correct
10 Correct 40 ms 25644 KB Output is correct
11 Correct 224 ms 56016 KB Output is correct
12 Correct 260 ms 55984 KB Output is correct
13 Correct 164 ms 66144 KB Output is correct
14 Correct 39 ms 25648 KB Output is correct
15 Correct 154 ms 52244 KB Output is correct
16 Correct 210 ms 44592 KB Output is correct
17 Correct 255 ms 50204 KB Output is correct
18 Correct 243 ms 49616 KB Output is correct
19 Correct 300 ms 61092 KB Output is correct
20 Correct 293 ms 60400 KB Output is correct
21 Correct 142 ms 40380 KB Output is correct
22 Correct 118 ms 40096 KB Output is correct
23 Correct 178 ms 47180 KB Output is correct
24 Correct 166 ms 46436 KB Output is correct
25 Correct 264 ms 54164 KB Output is correct
26 Correct 271 ms 49856 KB Output is correct
27 Correct 255 ms 49768 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 25260 KB Output is correct
2 Correct 47 ms 26700 KB Output is correct
3 Correct 44 ms 26588 KB Output is correct
4 Correct 58 ms 26988 KB Output is correct
5 Correct 50 ms 27004 KB Output is correct
6 Correct 46 ms 26424 KB Output is correct
7 Correct 37 ms 25652 KB Output is correct
8 Correct 105 ms 39128 KB Output is correct
9 Correct 112 ms 39092 KB Output is correct
10 Correct 40 ms 25644 KB Output is correct
11 Correct 224 ms 56016 KB Output is correct
12 Correct 260 ms 55984 KB Output is correct
13 Correct 164 ms 66144 KB Output is correct
14 Correct 39 ms 25648 KB Output is correct
15 Correct 154 ms 52244 KB Output is correct
16 Correct 210 ms 44592 KB Output is correct
17 Correct 255 ms 50204 KB Output is correct
18 Correct 243 ms 49616 KB Output is correct
19 Correct 300 ms 61092 KB Output is correct
20 Correct 293 ms 60400 KB Output is correct
21 Correct 142 ms 40380 KB Output is correct
22 Correct 118 ms 40096 KB Output is correct
23 Correct 178 ms 47180 KB Output is correct
24 Correct 166 ms 46436 KB Output is correct
25 Correct 264 ms 54164 KB Output is correct
26 Correct 271 ms 49856 KB Output is correct
27 Correct 255 ms 49768 KB Output is correct
28 Incorrect 40 ms 25676 KB Extra information in the output file
29 Halted 0 ms 0 KB -