oj.uz

Submission #533009

# Submission time Handle Problem Language Result Execution time Memory
533009 2022-03-04T10:52:18 Z Sohsoh84 Inside information (BOI21_servers) C++17
50 / 100
 922 ms 148216 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 = 2e5 + 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];

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;
}

void dfs(int v, int p, bool inc, bool dec, int p_w, int init_w, int rt) {
	if (inc) {
		if (rt) ans[rt][p_w]++;
		//fenwick::add(init_w, 1);
	}

	if (dec) {
		if (rt) ans[v][init_w]++;
		//ans[v][p_w] += fenwick::hist.size() - fenwick::query(init_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, rt);
	}
}

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

	fenwick::reset();
	for (auto [u, w] : adj[v])
		if (!B[u])
			dfs(u, v, true, true, w, w, v);

	reverse(all(adj[v]));
	fenwick::reset();
	for (auto [u, w] : adj[v])
		if (!B[u])
			dfs(u, v, true, true, w, w, 0);

	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]);
		}
	}

	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 52 ms 16980 KB Output is correct
2 Correct 69 ms 18604 KB Output is correct
3 Correct 81 ms 18584 KB Output is correct
4 Correct 75 ms 18632 KB Output is correct
5 Correct 70 ms 18684 KB Output is correct
6 Correct 60 ms 18400 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 16980 KB Output is correct
2 Correct 69 ms 18604 KB Output is correct
3 Correct 81 ms 18584 KB Output is correct
4 Correct 75 ms 18632 KB Output is correct
5 Correct 70 ms 18684 KB Output is correct
6 Correct 60 ms 18400 KB Output is correct
7 Incorrect 53 ms 16952 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 49 ms 16964 KB Output is correct
2 Correct 311 ms 63700 KB Output is correct
3 Correct 310 ms 63616 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 16964 KB Output is correct
2 Correct 311 ms 63700 KB Output is correct
3 Correct 310 ms 63616 KB Output is correct
4 Incorrect 54 ms 17036 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 46 ms 16952 KB Output is correct
2 Correct 386 ms 74348 KB Output is correct
3 Correct 407 ms 74344 KB Output is correct
4 Correct 549 ms 148216 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16952 KB Output is correct
2 Correct 386 ms 74348 KB Output is correct
3 Correct 407 ms 74344 KB Output is correct
4 Correct 549 ms 148216 KB Output is correct
5 Incorrect 53 ms 16960 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 44 ms 16896 KB Output is correct
2 Correct 554 ms 136620 KB Output is correct
3 Correct 378 ms 72156 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16896 KB Output is correct
2 Correct 554 ms 136620 KB Output is correct
3 Correct 378 ms 72156 KB Output is correct
4 Incorrect 45 ms 17056 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 48 ms 16992 KB Output is correct
2 Correct 433 ms 74356 KB Output is correct
3 Correct 391 ms 74400 KB Output is correct
4 Correct 558 ms 148140 KB Output is correct
5 Correct 48 ms 16952 KB Output is correct
6 Correct 535 ms 136548 KB Output is correct
7 Correct 398 ms 72328 KB Output is correct
8 Correct 428 ms 70744 KB Output is correct
9 Correct 491 ms 70900 KB Output is correct
10 Correct 835 ms 124516 KB Output is correct
11 Correct 885 ms 124436 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 16992 KB Output is correct
2 Correct 433 ms 74356 KB Output is correct
3 Correct 391 ms 74400 KB Output is correct
4 Correct 558 ms 148140 KB Output is correct
5 Correct 48 ms 16952 KB Output is correct
6 Correct 535 ms 136548 KB Output is correct
7 Correct 398 ms 72328 KB Output is correct
8 Correct 428 ms 70744 KB Output is correct
9 Correct 491 ms 70900 KB Output is correct
10 Correct 835 ms 124516 KB Output is correct
11 Correct 885 ms 124436 KB Output is correct
12 Incorrect 48 ms 17040 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 47 ms 16952 KB Output is correct
2 Correct 64 ms 18488 KB Output is correct
3 Correct 65 ms 18644 KB Output is correct
4 Correct 82 ms 18608 KB Output is correct
5 Correct 67 ms 18716 KB Output is correct
6 Correct 59 ms 18396 KB Output is correct
7 Correct 47 ms 16960 KB Output is correct
8 Correct 302 ms 63688 KB Output is correct
9 Correct 314 ms 63680 KB Output is correct
10 Correct 43 ms 17008 KB Output is correct
11 Correct 388 ms 74356 KB Output is correct
12 Correct 398 ms 74348 KB Output is correct
13 Correct 524 ms 148072 KB Output is correct
14 Correct 48 ms 17204 KB Output is correct
15 Correct 559 ms 136976 KB Output is correct
16 Correct 397 ms 72632 KB Output is correct
17 Correct 430 ms 71196 KB Output is correct
18 Correct 481 ms 71216 KB Output is correct
19 Correct 829 ms 124820 KB Output is correct
20 Correct 922 ms 124904 KB Output is correct
21 Correct 358 ms 66940 KB Output is correct
22 Correct 334 ms 67864 KB Output is correct
23 Correct 369 ms 71612 KB Output is correct
24 Correct 367 ms 71668 KB Output is correct
25 Correct 494 ms 75016 KB Output is correct
26 Correct 622 ms 94808 KB Output is correct
27 Correct 710 ms 99920 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16952 KB Output is correct
2 Correct 64 ms 18488 KB Output is correct
3 Correct 65 ms 18644 KB Output is correct
4 Correct 82 ms 18608 KB Output is correct
5 Correct 67 ms 18716 KB Output is correct
6 Correct 59 ms 18396 KB Output is correct
7 Correct 47 ms 16960 KB Output is correct
8 Correct 302 ms 63688 KB Output is correct
9 Correct 314 ms 63680 KB Output is correct
10 Correct 43 ms 17008 KB Output is correct
11 Correct 388 ms 74356 KB Output is correct
12 Correct 398 ms 74348 KB Output is correct
13 Correct 524 ms 148072 KB Output is correct
14 Correct 48 ms 17204 KB Output is correct
15 Correct 559 ms 136976 KB Output is correct
16 Correct 397 ms 72632 KB Output is correct
17 Correct 430 ms 71196 KB Output is correct
18 Correct 481 ms 71216 KB Output is correct
19 Correct 829 ms 124820 KB Output is correct
20 Correct 922 ms 124904 KB Output is correct
21 Correct 358 ms 66940 KB Output is correct
22 Correct 334 ms 67864 KB Output is correct
23 Correct 369 ms 71612 KB Output is correct
24 Correct 367 ms 71668 KB Output is correct
25 Correct 494 ms 75016 KB Output is correct
26 Correct 622 ms 94808 KB Output is correct
27 Correct 710 ms 99920 KB Output is correct
28 Incorrect 48 ms 17176 KB Extra information in the output file
29 Halted 0 ms 0 KB -