oj.uz

Submission #532992

# Submission time Handle Problem Language Result Execution time Memory
532992 2022-03-04T10:11:37 Z Sohsoh84 Inside information (BOI21_servers) C++17
50 / 100
 294 ms 54868 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;

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) {
		for (++ind; ind < MAXN; ind += ind & -ind) 
			fen[ind] += val;
		if (save_hist) hist.push_back({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) {
	if (dec) fenwick::add(init_w, 1);
	if (inc) ans[v][p_w] += fenwick::query(init_w - 1);

	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 (pll e : fenwick::hist)
		ans[v][e.X]++;

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

	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 45 ms 16820 KB Output is correct
2 Correct 54 ms 17640 KB Output is correct
3 Correct 55 ms 17780 KB Output is correct
4 Correct 69 ms 17736 KB Output is correct
5 Correct 62 ms 18004 KB Output is correct
6 Correct 69 ms 17692 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16820 KB Output is correct
2 Correct 54 ms 17640 KB Output is correct
3 Correct 55 ms 17780 KB Output is correct
4 Correct 69 ms 17736 KB Output is correct
5 Correct 62 ms 18004 KB Output is correct
6 Correct 69 ms 17692 KB Output is correct
7 Runtime error 36 ms 32564 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16772 KB Output is correct
2 Correct 183 ms 45372 KB Output is correct
3 Correct 195 ms 47728 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16772 KB Output is correct
2 Correct 183 ms 45372 KB Output is correct
3 Correct 195 ms 47728 KB Output is correct
4 Runtime error 36 ms 33080 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16852 KB Output is correct
2 Correct 166 ms 52076 KB Output is correct
3 Correct 165 ms 54808 KB Output is correct
4 Correct 203 ms 54648 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16852 KB Output is correct
2 Correct 166 ms 52076 KB Output is correct
3 Correct 165 ms 54808 KB Output is correct
4 Correct 203 ms 54648 KB Output is correct
5 Runtime error 37 ms 33064 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16820 KB Output is correct
2 Correct 174 ms 45396 KB Output is correct
3 Correct 175 ms 45896 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16820 KB Output is correct
2 Correct 174 ms 45396 KB Output is correct
3 Correct 175 ms 45896 KB Output is correct
4 Runtime error 35 ms 33024 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16860 KB Output is correct
2 Correct 172 ms 51960 KB Output is correct
3 Correct 165 ms 54800 KB Output is correct
4 Correct 208 ms 54868 KB Output is correct
5 Correct 43 ms 17228 KB Output is correct
6 Correct 180 ms 48060 KB Output is correct
7 Correct 165 ms 48568 KB Output is correct
8 Correct 216 ms 48984 KB Output is correct
9 Correct 186 ms 49012 KB Output is correct
10 Correct 218 ms 52856 KB Output is correct
11 Correct 294 ms 52348 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16860 KB Output is correct
2 Correct 172 ms 51960 KB Output is correct
3 Correct 165 ms 54800 KB Output is correct
4 Correct 208 ms 54868 KB Output is correct
5 Correct 43 ms 17228 KB Output is correct
6 Correct 180 ms 48060 KB Output is correct
7 Correct 165 ms 48568 KB Output is correct
8 Correct 216 ms 48984 KB Output is correct
9 Correct 186 ms 49012 KB Output is correct
10 Correct 218 ms 52856 KB Output is correct
11 Correct 294 ms 52348 KB Output is correct
12 Runtime error 36 ms 33084 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16824 KB Output is correct
2 Correct 57 ms 17560 KB Output is correct
3 Correct 52 ms 17724 KB Output is correct
4 Correct 65 ms 17732 KB Output is correct
5 Correct 59 ms 18020 KB Output is correct
6 Correct 56 ms 17696 KB Output is correct
7 Correct 47 ms 16892 KB Output is correct
8 Correct 190 ms 45412 KB Output is correct
9 Correct 182 ms 47692 KB Output is correct
10 Correct 43 ms 17224 KB Output is correct
11 Correct 180 ms 54868 KB Output is correct
12 Correct 167 ms 54764 KB Output is correct
13 Correct 208 ms 54808 KB Output is correct
14 Correct 55 ms 17216 KB Output is correct
15 Correct 179 ms 48264 KB Output is correct
16 Correct 170 ms 48652 KB Output is correct
17 Correct 199 ms 49036 KB Output is correct
18 Correct 198 ms 49096 KB Output is correct
19 Correct 214 ms 52852 KB Output is correct
20 Correct 292 ms 52328 KB Output is correct
21 Correct 180 ms 48272 KB Output is correct
22 Correct 180 ms 48300 KB Output is correct
23 Correct 182 ms 48600 KB Output is correct
24 Correct 176 ms 48672 KB Output is correct
25 Correct 199 ms 49788 KB Output is correct
26 Correct 169 ms 48220 KB Output is correct
27 Correct 153 ms 48208 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16824 KB Output is correct
2 Correct 57 ms 17560 KB Output is correct
3 Correct 52 ms 17724 KB Output is correct
4 Correct 65 ms 17732 KB Output is correct
5 Correct 59 ms 18020 KB Output is correct
6 Correct 56 ms 17696 KB Output is correct
7 Correct 47 ms 16892 KB Output is correct
8 Correct 190 ms 45412 KB Output is correct
9 Correct 182 ms 47692 KB Output is correct
10 Correct 43 ms 17224 KB Output is correct
11 Correct 180 ms 54868 KB Output is correct
12 Correct 167 ms 54764 KB Output is correct
13 Correct 208 ms 54808 KB Output is correct
14 Correct 55 ms 17216 KB Output is correct
15 Correct 179 ms 48264 KB Output is correct
16 Correct 170 ms 48652 KB Output is correct
17 Correct 199 ms 49036 KB Output is correct
18 Correct 198 ms 49096 KB Output is correct
19 Correct 214 ms 52852 KB Output is correct
20 Correct 292 ms 52328 KB Output is correct
21 Correct 180 ms 48272 KB Output is correct
22 Correct 180 ms 48300 KB Output is correct
23 Correct 182 ms 48600 KB Output is correct
24 Correct 176 ms 48672 KB Output is correct
25 Correct 199 ms 49788 KB Output is correct
26 Correct 169 ms 48220 KB Output is correct
27 Correct 153 ms 48208 KB Output is correct
28 Runtime error 36 ms 33056 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -