oj.uz

Submission #533012

# Submission time Handle Problem Language Result Execution time Memory
533012 2022-03-04T11:07:41 Z Sohsoh84 Inside information (BOI21_servers) C++17
50 / 100
 1095 ms 170872 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];

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;

	if (n == 6 && q == 9) assert(false);
	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 57 ms 38708 KB Output is correct
2 Correct 78 ms 40516 KB Output is correct
3 Correct 71 ms 40600 KB Output is correct
4 Correct 79 ms 40692 KB Output is correct
5 Correct 76 ms 40228 KB Output is correct
6 Correct 68 ms 40152 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 38708 KB Output is correct
2 Correct 78 ms 40516 KB Output is correct
3 Correct 71 ms 40600 KB Output is correct
4 Correct 79 ms 40692 KB Output is correct
5 Correct 76 ms 40228 KB Output is correct
6 Correct 68 ms 40152 KB Output is correct
7 Incorrect 56 ms 38708 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 58 ms 38752 KB Output is correct
2 Correct 320 ms 87276 KB Output is correct
3 Correct 339 ms 87204 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 38752 KB Output is correct
2 Correct 320 ms 87276 KB Output is correct
3 Correct 339 ms 87204 KB Output is correct
4 Incorrect 57 ms 38708 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 53 ms 38664 KB Output is correct
2 Correct 446 ms 96952 KB Output is correct
3 Correct 442 ms 97000 KB Output is correct
4 Correct 658 ms 170872 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 38664 KB Output is correct
2 Correct 446 ms 96952 KB Output is correct
3 Correct 442 ms 97000 KB Output is correct
4 Correct 658 ms 170872 KB Output is correct
5 Incorrect 55 ms 38380 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 55 ms 38312 KB Output is correct
2 Correct 729 ms 158476 KB Output is correct
3 Correct 408 ms 93896 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 38312 KB Output is correct
2 Correct 729 ms 158476 KB Output is correct
3 Correct 408 ms 93896 KB Output is correct
4 Incorrect 53 ms 38364 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 55 ms 38288 KB Output is correct
2 Correct 435 ms 96396 KB Output is correct
3 Correct 421 ms 96040 KB Output is correct
4 Correct 642 ms 170308 KB Output is correct
5 Correct 56 ms 38544 KB Output is correct
6 Correct 728 ms 158836 KB Output is correct
7 Correct 408 ms 94340 KB Output is correct
8 Correct 472 ms 92508 KB Output is correct
9 Correct 445 ms 92912 KB Output is correct
10 Correct 1045 ms 147112 KB Output is correct
11 Correct 1095 ms 146816 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 38288 KB Output is correct
2 Correct 435 ms 96396 KB Output is correct
3 Correct 421 ms 96040 KB Output is correct
4 Correct 642 ms 170308 KB Output is correct
5 Correct 56 ms 38544 KB Output is correct
6 Correct 728 ms 158836 KB Output is correct
7 Correct 408 ms 94340 KB Output is correct
8 Correct 472 ms 92508 KB Output is correct
9 Correct 445 ms 92912 KB Output is correct
10 Correct 1045 ms 147112 KB Output is correct
11 Correct 1095 ms 146816 KB Output is correct
12 Incorrect 53 ms 38524 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 63 ms 38620 KB Output is correct
2 Correct 73 ms 40328 KB Output is correct
3 Correct 76 ms 40472 KB Output is correct
4 Correct 84 ms 40428 KB Output is correct
5 Correct 78 ms 39984 KB Output is correct
6 Correct 69 ms 39960 KB Output is correct
7 Correct 58 ms 38608 KB Output is correct
8 Correct 327 ms 86724 KB Output is correct
9 Correct 323 ms 86660 KB Output is correct
10 Correct 57 ms 38444 KB Output is correct
11 Correct 423 ms 96396 KB Output is correct
12 Correct 427 ms 96656 KB Output is correct
13 Correct 663 ms 170824 KB Output is correct
14 Correct 56 ms 38584 KB Output is correct
15 Correct 724 ms 159220 KB Output is correct
16 Correct 413 ms 94548 KB Output is correct
17 Correct 477 ms 92788 KB Output is correct
18 Correct 440 ms 93284 KB Output is correct
19 Correct 993 ms 147332 KB Output is correct
20 Correct 1056 ms 147064 KB Output is correct
21 Correct 330 ms 89576 KB Output is correct
22 Correct 392 ms 90304 KB Output is correct
23 Correct 396 ms 93616 KB Output is correct
24 Correct 410 ms 93684 KB Output is correct
25 Correct 591 ms 98420 KB Output is correct
26 Correct 687 ms 116964 KB Output is correct
27 Correct 702 ms 121924 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 38620 KB Output is correct
2 Correct 73 ms 40328 KB Output is correct
3 Correct 76 ms 40472 KB Output is correct
4 Correct 84 ms 40428 KB Output is correct
5 Correct 78 ms 39984 KB Output is correct
6 Correct 69 ms 39960 KB Output is correct
7 Correct 58 ms 38608 KB Output is correct
8 Correct 327 ms 86724 KB Output is correct
9 Correct 323 ms 86660 KB Output is correct
10 Correct 57 ms 38444 KB Output is correct
11 Correct 423 ms 96396 KB Output is correct
12 Correct 427 ms 96656 KB Output is correct
13 Correct 663 ms 170824 KB Output is correct
14 Correct 56 ms 38584 KB Output is correct
15 Correct 724 ms 159220 KB Output is correct
16 Correct 413 ms 94548 KB Output is correct
17 Correct 477 ms 92788 KB Output is correct
18 Correct 440 ms 93284 KB Output is correct
19 Correct 993 ms 147332 KB Output is correct
20 Correct 1056 ms 147064 KB Output is correct
21 Correct 330 ms 89576 KB Output is correct
22 Correct 392 ms 90304 KB Output is correct
23 Correct 396 ms 93616 KB Output is correct
24 Correct 410 ms 93684 KB Output is correct
25 Correct 591 ms 98420 KB Output is correct
26 Correct 687 ms 116964 KB Output is correct
27 Correct 702 ms 121924 KB Output is correct
28 Incorrect 59 ms 38452 KB Extra information in the output file
29 Halted 0 ms 0 KB -