oj.uz

Submission #533014

# Submission time Handle Problem Language Result Execution time Memory
533014 2022-03-04T11:39:11 Z Sohsoh84 Inside information (BOI21_servers) C++17
50 / 100
 740 ms 100700 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;
#define	wtf(x)			cerr << #x << ": "; for (pll e : x) cerr << e.X << sep << e.Y << endl;

const ll MAXN = 5e5 + 10;
const ll LOG = 20;

namespace fenwick {
	int fen[MAXN];
	vector<pll> hist;
	
	inline void add(int ind, int val, bool save_hist = true) {	
		if (save_hist) hist.push_back({ind, val});
		for (++ind; ind < MAXN; ind += ind & -ind) 
			fen[ind] += val;
	}

	inline int query(int ind) {
		int ans = 0;
		for (++ind; ind > 0; ind -= ind & -ind)
			ans += fen[ind];
		return ans;
	}

	inline void reset() {
		for (pll e : hist)
			add(e.X, -e.Y, false);
		hist.clear();
	}
}

int n, q, p_w[MAXN], dp[MAXN], sz[MAXN], par[MAXN][LOG], last_edge[MAXN][LOG], H[MAXN];
map<int, int> ans[MAXN];
vector<pll> adj[MAXN];
vector<pair<int, pll>> Q; // time, query
bool B[MAXN], dec_lift[MAXN][LOG], inc_lift[MAXN][LOG];
vector<int> tmp;

void pre_dfs(int v, int p) {
	H[v] = H[p] + 1;
	for (auto [u, w] : adj[v]) {
		if (u != p) {
			pre_dfs(u, v);
			par[u][0] = v;
			last_edge[u][0] = w;
			inc_lift[u][0] = dec_lift[u][0] = true;
		}
	}
}

inline int Par(int v, int k) {
	for (int i = LOG - 1; i >= 0; i--)
		if (k & (1 << i))
			v = par[v][i];
	return v;
}

inline int LCA(int u, int v) {
	if (H[u] > H[v]) swap(v, u);
	v = Par(v, H[v] - H[u]);
	if (v == u) return v;

	for (int i = LOG - 1; i >= 0; i--)
		if (par[v][i] != par[u][i])
			v = par[v][i], u = par[u][i];

	return par[v][0];
}

inline int last_edge_lift(int v, int k) {
	int ans = 0;
	for (int i = 0; i < LOG; i++)
		if (k & (1 << i))
			ans = last_edge[v][i], v = par[v][i];
	return ans;
}

inline bool is_dec(int v, int k) {
	int w = MAXN * 2;
	for (int i = 0; i < LOG; i++) {
		if (k & (1 << i)) {
			if (!dec_lift[v][i] || w < last_edge[v][0])
				return false;

			w = last_edge[v][i];
			v = par[v][i];
		}
	}

	return true;
}

inline bool is_inc(int v, int k) {
	int w = -1;
	for (int i = 0; i < LOG; i++) {
		if (k & (1 << i)) {
			if (!inc_lift[v][i] || w > last_edge[v][0])
				return false;

			w = last_edge[v][i];
			v = par[v][i];
		}
	}

	return true;
}

int sub_sz(int v, int p) {
	sz[v] = 1;
	for (auto [u, w] : adj[v])
		if (u != p && !B[u])
			sz[v] += sub_sz(u, v);

	return sz[v];
}

int find_centroid(int v, int p, int n) {
	for (auto [u, w] : adj[v])
		if (sz[u] * 2 > n && !B[u] && u != p)
			return find_centroid(u, v, n);

	return v;
}

inline int inv(int x) {
	return MAXN - 2 - x;
}

void dfs(int v, int p, bool inc, bool dec, int p_w, int init_w) {
	if (dec) 
		tmp.push_back(init_w);

	if (inc)
		ans[v][inv(p_w)] += fenwick::query(p_w);

	for (auto [u, w] : adj[v]) {
		if (B[u] || u == p) continue;
		dfs(u, v, inc && w > p_w, dec && w < p_w, w, init_w);
	}
}

inline void solve(int v) {
	v = find_centroid(v, 0, sub_sz(v, 0));
	B[v] = true;

	fenwick::reset();
	fenwick::add(0, 1);
	for (auto [u, w] : adj[v]) {
		if (!B[u])
			dfs(u, v, true, true, w, w);
		for (int e : tmp)
			fenwick::add(e, 1);
		tmp.clear();
	}
	
	for (pll e : fenwick::hist)
		ans[v][inv(e.X)]++;
	ans[v][0]++;

	reverse(all(adj[v]));
	fenwick::reset();
	for (auto [u, w] : adj[v]) {
		if (!B[u])
			dfs(u, v, true, true, w, w);
		for (int e : tmp)
			fenwick::add(e, 1);
		tmp.clear();
	}

	for (auto [u, w] : adj[v])
		if (!B[u])
			solve(u);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> q;

	for (int i = 1; i <= n + q - 1; i++) {
		char c;
		cin >> c;
		if (c == 'S') {
			int u, v;
			cin >> u >> v;
			adj[u].push_back({v, i});
			adj[v].push_back({u, i});
		} else if (c == 'Q') {
			int u, v;
			cin >> u >> v;
			Q.push_back({i, {v, u}});
		} else {
			int v;
			cin >> v;
			Q.push_back({i, {-1, v}});
		}
	}

	pre_dfs(1, 0);
	for (int i = 1; i < LOG; i++) {
		for (int v = 1; v <= n; v++) {
			int p = par[v][i - 1];
			par[v][i] = par[p][i - 1];
			last_edge[v][i] = last_edge[p][i - 1];
			inc_lift[v][i] = (inc_lift[v][i - 1] && inc_lift[p][i - 1] && last_edge[v][i - 1] < last_edge[p][0]);
			dec_lift[v][i] = (dec_lift[v][i - 1] && dec_lift[p][i - 1] && last_edge[v][i - 1] > last_edge[p][0]);
		}
	}

	for (int v = 1; v <= n; v++)
		for (pll& e : adj[v])
			e.Y = inv(e.Y);
	solve(1);
	for (int v = 1; v <= n; v++) {
		int ps = 0;
		for (pll e : ans[v]) {
			ps += e.Y;
			ans[v][e.X] = ps;
		} // optimize
	}

	for (auto [t, e] : Q) {
		int u = e.X, v = e.Y;
		if (u >= 0) {
			int lca = LCA(e.X, e.Y);
			int lst = 0, lst_u = last_edge_lift(u, H[u] - H[lca]), lst_v = last_edge_lift(v, H[v] - H[lca]);
			lst = lst_u;
			if (v != lca) lst = last_edge[v][0];
			cout << (lst <= t && is_inc(u, H[u] - H[lca]) && is_dec(v, H[v] - H[lca]) 
					&& (!lst_v || !lst_u || lst_u < lst_v) ? "yes" : "no") << endl;
		} else {
			cout << prev(ans[v].upper_bound(t)) -> Y << endl;
		}
	}
	return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 38708 KB Output is correct
2 Correct 72 ms 40892 KB Output is correct
3 Correct 88 ms 41064 KB Output is correct
4 Correct 76 ms 41116 KB Output is correct
5 Correct 85 ms 40696 KB Output is correct
6 Correct 72 ms 40664 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 38708 KB Output is correct
2 Correct 72 ms 40892 KB Output is correct
3 Correct 88 ms 41064 KB Output is correct
4 Correct 76 ms 41116 KB Output is correct
5 Correct 85 ms 40696 KB Output is correct
6 Correct 72 ms 40664 KB Output is correct
7 Incorrect 61 ms 38680 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 52 ms 38724 KB Output is correct
2 Correct 341 ms 93944 KB Output is correct
3 Correct 344 ms 93936 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 38724 KB Output is correct
2 Correct 341 ms 93944 KB Output is correct
3 Correct 344 ms 93936 KB Output is correct
4 Incorrect 61 ms 38764 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 51 ms 38760 KB Output is correct
2 Correct 433 ms 100032 KB Output is correct
3 Correct 444 ms 100104 KB Output is correct
4 Correct 473 ms 100672 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 38760 KB Output is correct
2 Correct 433 ms 100032 KB Output is correct
3 Correct 444 ms 100104 KB Output is correct
4 Correct 473 ms 100672 KB Output is correct
5 Incorrect 50 ms 38652 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 54 ms 38720 KB Output is correct
2 Correct 428 ms 93760 KB Output is correct
3 Correct 380 ms 93912 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 38720 KB Output is correct
2 Correct 428 ms 93760 KB Output is correct
3 Correct 380 ms 93912 KB Output is correct
4 Incorrect 60 ms 38752 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 64 ms 38736 KB Output is correct
2 Correct 451 ms 100080 KB Output is correct
3 Correct 432 ms 100200 KB Output is correct
4 Correct 476 ms 100700 KB Output is correct
5 Correct 55 ms 38712 KB Output is correct
6 Correct 434 ms 93760 KB Output is correct
7 Correct 412 ms 93884 KB Output is correct
8 Correct 485 ms 93688 KB Output is correct
9 Correct 477 ms 94092 KB Output is correct
10 Correct 655 ms 98852 KB Output is correct
11 Correct 693 ms 98452 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 64 ms 38736 KB Output is correct
2 Correct 451 ms 100080 KB Output is correct
3 Correct 432 ms 100200 KB Output is correct
4 Correct 476 ms 100700 KB Output is correct
5 Correct 55 ms 38712 KB Output is correct
6 Correct 434 ms 93760 KB Output is correct
7 Correct 412 ms 93884 KB Output is correct
8 Correct 485 ms 93688 KB Output is correct
9 Correct 477 ms 94092 KB Output is correct
10 Correct 655 ms 98852 KB Output is correct
11 Correct 693 ms 98452 KB Output is correct
12 Incorrect 51 ms 38684 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 55 ms 38756 KB Output is correct
2 Correct 92 ms 40928 KB Output is correct
3 Correct 77 ms 41052 KB Output is correct
4 Correct 83 ms 41028 KB Output is correct
5 Correct 77 ms 40760 KB Output is correct
6 Correct 76 ms 40704 KB Output is correct
7 Correct 61 ms 38708 KB Output is correct
8 Correct 347 ms 94012 KB Output is correct
9 Correct 354 ms 93932 KB Output is correct
10 Correct 55 ms 38732 KB Output is correct
11 Correct 414 ms 99996 KB Output is correct
12 Correct 453 ms 100044 KB Output is correct
13 Correct 423 ms 100688 KB Output is correct
14 Correct 56 ms 38884 KB Output is correct
15 Correct 428 ms 93860 KB Output is correct
16 Correct 386 ms 93836 KB Output is correct
17 Correct 470 ms 93656 KB Output is correct
18 Correct 430 ms 94104 KB Output is correct
19 Correct 633 ms 98824 KB Output is correct
20 Correct 740 ms 98552 KB Output is correct
21 Correct 391 ms 94432 KB Output is correct
22 Correct 412 ms 94100 KB Output is correct
23 Correct 402 ms 93900 KB Output is correct
24 Correct 367 ms 93948 KB Output is correct
25 Correct 610 ms 100248 KB Output is correct
26 Correct 530 ms 93360 KB Output is correct
27 Correct 464 ms 93356 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 38756 KB Output is correct
2 Correct 92 ms 40928 KB Output is correct
3 Correct 77 ms 41052 KB Output is correct
4 Correct 83 ms 41028 KB Output is correct
5 Correct 77 ms 40760 KB Output is correct
6 Correct 76 ms 40704 KB Output is correct
7 Correct 61 ms 38708 KB Output is correct
8 Correct 347 ms 94012 KB Output is correct
9 Correct 354 ms 93932 KB Output is correct
10 Correct 55 ms 38732 KB Output is correct
11 Correct 414 ms 99996 KB Output is correct
12 Correct 453 ms 100044 KB Output is correct
13 Correct 423 ms 100688 KB Output is correct
14 Correct 56 ms 38884 KB Output is correct
15 Correct 428 ms 93860 KB Output is correct
16 Correct 386 ms 93836 KB Output is correct
17 Correct 470 ms 93656 KB Output is correct
18 Correct 430 ms 94104 KB Output is correct
19 Correct 633 ms 98824 KB Output is correct
20 Correct 740 ms 98552 KB Output is correct
21 Correct 391 ms 94432 KB Output is correct
22 Correct 412 ms 94100 KB Output is correct
23 Correct 402 ms 93900 KB Output is correct
24 Correct 367 ms 93948 KB Output is correct
25 Correct 610 ms 100248 KB Output is correct
26 Correct 530 ms 93360 KB Output is correct
27 Correct 464 ms 93356 KB Output is correct
28 Incorrect 63 ms 38716 KB Extra information in the output file
29 Halted 0 ms 0 KB -