oj.uz

답안 #528501

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
528501 2022-02-20T11:56:06 Z koioi.org-koosaga Inside information (BOI21_servers) C++17
52.5 / 100
 3500 ms 71056 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 ans[MAXN];
	struct query{
		int s, e, idx;
	};
	vector<query> qry[MAXN];
	void query(int v, int hi, int stackIdx){
		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[stackIdx]++;
			qry[w].push_back({lo, hi, stackIdx});
		}
	}
	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;
	}
	vector<int> sweep(int n, int q){
		for(int i = 1; i <= n; i++){
			for(auto &j : qry[i]){
				for(auto &k : ds[i]){
					if(j.s <= k.first && k.second <= j.e) ans[j.idx]++;
				}
			}
		}
		return vector<int>(ans, ans + q);
	}
};

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 == 2) CD::query(i.u, i.lim, i.idx);
	}
	auto swp = CD::sweep(n, sz(qry));
	for(auto &i : qry){
		if(i.t == 1) cout << (CD::reach(i.u, i.v, i.lim) ? "yes" : "no") << "\n";
		else cout << swp[i.idx] << "\n";
	}
}

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 28284 KB Output is correct
2 Correct 55 ms 28820 KB Output is correct
3 Correct 47 ms 28720 KB Output is correct
4 Correct 51 ms 28984 KB Output is correct
5 Correct 55 ms 29184 KB Output is correct
6 Correct 50 ms 28552 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 28284 KB Output is correct
2 Correct 55 ms 28820 KB Output is correct
3 Correct 47 ms 28720 KB Output is correct
4 Correct 51 ms 28984 KB Output is correct
5 Correct 55 ms 29184 KB Output is correct
6 Correct 50 ms 28552 KB Output is correct
7 Correct 45 ms 28844 KB Output is correct
8 Correct 58 ms 30984 KB Output is correct
9 Correct 148 ms 31236 KB Output is correct
10 Correct 68 ms 31236 KB Output is correct
11 Correct 65 ms 32060 KB Output is correct
12 Correct 518 ms 30884 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 28344 KB Output is correct
2 Correct 110 ms 39312 KB Output is correct
3 Correct 110 ms 39364 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 28344 KB Output is correct
2 Correct 110 ms 39312 KB Output is correct
3 Correct 110 ms 39364 KB Output is correct
4 Correct 43 ms 28724 KB Output is correct
5 Correct 2924 ms 39828 KB Output is correct
6 Execution timed out 3596 ms 41404 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 28336 KB Output is correct
2 Correct 277 ms 56804 KB Output is correct
3 Correct 242 ms 56804 KB Output is correct
4 Correct 169 ms 66916 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 28336 KB Output is correct
2 Correct 277 ms 56804 KB Output is correct
3 Correct 242 ms 56804 KB Output is correct
4 Correct 169 ms 66916 KB Output is correct
5 Correct 43 ms 28752 KB Output is correct
6 Correct 337 ms 58804 KB Output is correct
7 Execution timed out 3513 ms 70960 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 28312 KB Output is correct
2 Correct 161 ms 53016 KB Output is correct
3 Correct 238 ms 45336 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 28312 KB Output is correct
2 Correct 161 ms 53016 KB Output is correct
3 Correct 238 ms 45336 KB Output is correct
4 Correct 41 ms 28848 KB Output is correct
5 Execution timed out 3512 ms 59188 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 28272 KB Output is correct
2 Correct 309 ms 56788 KB Output is correct
3 Correct 256 ms 56932 KB Output is correct
4 Correct 175 ms 66968 KB Output is correct
5 Correct 43 ms 28284 KB Output is correct
6 Correct 169 ms 52944 KB Output is correct
7 Correct 217 ms 45392 KB Output is correct
8 Correct 246 ms 50768 KB Output is correct
9 Correct 246 ms 50384 KB Output is correct
10 Correct 321 ms 61808 KB Output is correct
11 Correct 348 ms 61192 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 28272 KB Output is correct
2 Correct 309 ms 56788 KB Output is correct
3 Correct 256 ms 56932 KB Output is correct
4 Correct 175 ms 66968 KB Output is correct
5 Correct 43 ms 28284 KB Output is correct
6 Correct 169 ms 52944 KB Output is correct
7 Correct 217 ms 45392 KB Output is correct
8 Correct 246 ms 50768 KB Output is correct
9 Correct 246 ms 50384 KB Output is correct
10 Correct 321 ms 61808 KB Output is correct
11 Correct 348 ms 61192 KB Output is correct
12 Correct 43 ms 28848 KB Output is correct
13 Correct 259 ms 58832 KB Output is correct
14 Execution timed out 3517 ms 71056 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 28360 KB Output is correct
2 Correct 51 ms 28876 KB Output is correct
3 Correct 48 ms 28804 KB Output is correct
4 Correct 54 ms 28988 KB Output is correct
5 Correct 52 ms 29168 KB Output is correct
6 Correct 44 ms 28632 KB Output is correct
7 Correct 43 ms 28116 KB Output is correct
8 Correct 118 ms 39356 KB Output is correct
9 Correct 117 ms 39364 KB Output is correct
10 Correct 43 ms 28160 KB Output is correct
11 Correct 263 ms 56920 KB Output is correct
12 Correct 239 ms 56940 KB Output is correct
13 Correct 168 ms 66984 KB Output is correct
14 Correct 42 ms 28208 KB Output is correct
15 Correct 160 ms 53036 KB Output is correct
16 Correct 225 ms 45448 KB Output is correct
17 Correct 262 ms 50764 KB Output is correct
18 Correct 271 ms 50564 KB Output is correct
19 Correct 315 ms 61780 KB Output is correct
20 Correct 318 ms 61296 KB Output is correct
21 Correct 120 ms 40780 KB Output is correct
22 Correct 121 ms 40908 KB Output is correct
23 Correct 185 ms 47952 KB Output is correct
24 Correct 175 ms 47280 KB Output is correct
25 Correct 283 ms 54960 KB Output is correct
26 Correct 280 ms 50544 KB Output is correct
27 Correct 266 ms 50520 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 28360 KB Output is correct
2 Correct 51 ms 28876 KB Output is correct
3 Correct 48 ms 28804 KB Output is correct
4 Correct 54 ms 28988 KB Output is correct
5 Correct 52 ms 29168 KB Output is correct
6 Correct 44 ms 28632 KB Output is correct
7 Correct 43 ms 28116 KB Output is correct
8 Correct 118 ms 39356 KB Output is correct
9 Correct 117 ms 39364 KB Output is correct
10 Correct 43 ms 28160 KB Output is correct
11 Correct 263 ms 56920 KB Output is correct
12 Correct 239 ms 56940 KB Output is correct
13 Correct 168 ms 66984 KB Output is correct
14 Correct 42 ms 28208 KB Output is correct
15 Correct 160 ms 53036 KB Output is correct
16 Correct 225 ms 45448 KB Output is correct
17 Correct 262 ms 50764 KB Output is correct
18 Correct 271 ms 50564 KB Output is correct
19 Correct 315 ms 61780 KB Output is correct
20 Correct 318 ms 61296 KB Output is correct
21 Correct 120 ms 40780 KB Output is correct
22 Correct 121 ms 40908 KB Output is correct
23 Correct 185 ms 47952 KB Output is correct
24 Correct 175 ms 47280 KB Output is correct
25 Correct 283 ms 54960 KB Output is correct
26 Correct 280 ms 50544 KB Output is correct
27 Correct 266 ms 50520 KB Output is correct
28 Correct 45 ms 28848 KB Output is correct
29 Correct 56 ms 31092 KB Output is correct
30 Correct 145 ms 31128 KB Output is correct
31 Correct 55 ms 31216 KB Output is correct
32 Correct 55 ms 32060 KB Output is correct
33 Correct 525 ms 30892 KB Output is correct
34 Correct 41 ms 28604 KB Output is correct
35 Correct 2874 ms 39872 KB Output is correct
36 Execution timed out 3555 ms 41548 KB Time limit exceeded
37 Halted 0 ms 0 KB -