oj.uz

Submission #528493

# Submission time Handle Problem Language Result Execution time Memory
528493 2022-02-20T11:44:35 Z koioi.org-koosaga Inside information (BOI21_servers) C++17
0 / 100
 52 ms 25704 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 > 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
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 25648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 25648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 25620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 25620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 25604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 25604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 25616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 25616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 25704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 25704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 25636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 25636 KB Output isn't correct
2 Halted 0 ms 0 KB -