oj.uz

Submission #533010

# Submission time Handle Problem Language Result Execution time Memory
533010 2022-03-04T10:52:58 Z Sohsoh84 Inside information (BOI21_servers) C++17
50 / 100
 1082 ms 149892 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 59 ms 17580 KB Output is correct
2 Correct 67 ms 19712 KB Output is correct
3 Correct 85 ms 19724 KB Output is correct
4 Correct 73 ms 19744 KB Output is correct
5 Correct 64 ms 19332 KB Output is correct
6 Correct 59 ms 19288 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 17580 KB Output is correct
2 Correct 67 ms 19712 KB Output is correct
3 Correct 85 ms 19724 KB Output is correct
4 Correct 73 ms 19744 KB Output is correct
5 Correct 64 ms 19332 KB Output is correct
6 Correct 59 ms 19288 KB Output is correct
7 Incorrect 46 ms 17584 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 48 ms 17592 KB Output is correct
2 Correct 301 ms 65360 KB Output is correct
3 Correct 322 ms 65472 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 17592 KB Output is correct
2 Correct 301 ms 65360 KB Output is correct
3 Correct 322 ms 65472 KB Output is correct
4 Incorrect 49 ms 17492 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 45 ms 17580 KB Output is correct
2 Correct 405 ms 75076 KB Output is correct
3 Correct 421 ms 75488 KB Output is correct
4 Correct 613 ms 149892 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 17580 KB Output is correct
2 Correct 405 ms 75076 KB Output is correct
3 Correct 421 ms 75488 KB Output is correct
4 Correct 613 ms 149892 KB Output is correct
5 Incorrect 47 ms 17596 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 50 ms 17556 KB Output is correct
2 Correct 680 ms 137772 KB Output is correct
3 Correct 379 ms 72948 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 17556 KB Output is correct
2 Correct 680 ms 137772 KB Output is correct
3 Correct 379 ms 72948 KB Output is correct
4 Incorrect 43 ms 17460 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 46 ms 17616 KB Output is correct
2 Correct 481 ms 75036 KB Output is correct
3 Correct 417 ms 75436 KB Output is correct
4 Correct 638 ms 149676 KB Output is correct
5 Correct 45 ms 17588 KB Output is correct
6 Correct 661 ms 138112 KB Output is correct
7 Correct 442 ms 73348 KB Output is correct
8 Correct 454 ms 71512 KB Output is correct
9 Correct 457 ms 71880 KB Output is correct
10 Correct 957 ms 125444 KB Output is correct
11 Correct 1062 ms 125276 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 17616 KB Output is correct
2 Correct 481 ms 75036 KB Output is correct
3 Correct 417 ms 75436 KB Output is correct
4 Correct 638 ms 149676 KB Output is correct
5 Correct 45 ms 17588 KB Output is correct
6 Correct 661 ms 138112 KB Output is correct
7 Correct 442 ms 73348 KB Output is correct
8 Correct 454 ms 71512 KB Output is correct
9 Correct 457 ms 71880 KB Output is correct
10 Correct 957 ms 125444 KB Output is correct
11 Correct 1062 ms 125276 KB Output is correct
12 Incorrect 42 ms 17452 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 48 ms 17584 KB Output is correct
2 Correct 62 ms 19708 KB Output is correct
3 Correct 59 ms 19816 KB Output is correct
4 Correct 83 ms 19840 KB Output is correct
5 Correct 80 ms 19420 KB Output is correct
6 Correct 65 ms 19312 KB Output is correct
7 Correct 49 ms 17620 KB Output is correct
8 Correct 324 ms 65416 KB Output is correct
9 Correct 318 ms 65540 KB Output is correct
10 Correct 44 ms 17496 KB Output is correct
11 Correct 460 ms 75180 KB Output is correct
12 Correct 418 ms 75312 KB Output is correct
13 Correct 642 ms 149396 KB Output is correct
14 Correct 49 ms 17340 KB Output is correct
15 Correct 719 ms 137640 KB Output is correct
16 Correct 408 ms 73004 KB Output is correct
17 Correct 529 ms 71296 KB Output is correct
18 Correct 480 ms 71612 KB Output is correct
19 Correct 1042 ms 125324 KB Output is correct
20 Correct 1082 ms 125056 KB Output is correct
21 Correct 343 ms 68084 KB Output is correct
22 Correct 371 ms 68736 KB Output is correct
23 Correct 456 ms 71868 KB Output is correct
24 Correct 396 ms 72016 KB Output is correct
25 Correct 545 ms 75900 KB Output is correct
26 Correct 679 ms 95172 KB Output is correct
27 Correct 649 ms 100236 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 17584 KB Output is correct
2 Correct 62 ms 19708 KB Output is correct
3 Correct 59 ms 19816 KB Output is correct
4 Correct 83 ms 19840 KB Output is correct
5 Correct 80 ms 19420 KB Output is correct
6 Correct 65 ms 19312 KB Output is correct
7 Correct 49 ms 17620 KB Output is correct
8 Correct 324 ms 65416 KB Output is correct
9 Correct 318 ms 65540 KB Output is correct
10 Correct 44 ms 17496 KB Output is correct
11 Correct 460 ms 75180 KB Output is correct
12 Correct 418 ms 75312 KB Output is correct
13 Correct 642 ms 149396 KB Output is correct
14 Correct 49 ms 17340 KB Output is correct
15 Correct 719 ms 137640 KB Output is correct
16 Correct 408 ms 73004 KB Output is correct
17 Correct 529 ms 71296 KB Output is correct
18 Correct 480 ms 71612 KB Output is correct
19 Correct 1042 ms 125324 KB Output is correct
20 Correct 1082 ms 125056 KB Output is correct
21 Correct 343 ms 68084 KB Output is correct
22 Correct 371 ms 68736 KB Output is correct
23 Correct 456 ms 71868 KB Output is correct
24 Correct 396 ms 72016 KB Output is correct
25 Correct 545 ms 75900 KB Output is correct
26 Correct 679 ms 95172 KB Output is correct
27 Correct 649 ms 100236 KB Output is correct
28 Incorrect 50 ms 17296 KB Extra information in the output file
29 Halted 0 ms 0 KB -