oj.uz

Submission #533006

# Submission time Handle Problem Language Result Execution time Memory
533006 2022-03-04T10:49:05 Z Sohsoh84 Inside information (BOI21_servers) C++17
50 / 100
 403 ms 61128 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 47 ms 16784 KB Output is correct
2 Correct 82 ms 17936 KB Output is correct
3 Correct 57 ms 18036 KB Output is correct
4 Correct 92 ms 18088 KB Output is correct
5 Correct 77 ms 18260 KB Output is correct
6 Correct 59 ms 18012 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16784 KB Output is correct
2 Correct 82 ms 17936 KB Output is correct
3 Correct 57 ms 18036 KB Output is correct
4 Correct 92 ms 18088 KB Output is correct
5 Correct 77 ms 18260 KB Output is correct
6 Correct 59 ms 18012 KB Output is correct
7 Incorrect 45 ms 16780 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 43 ms 16840 KB Output is correct
2 Correct 224 ms 52412 KB Output is correct
3 Correct 231 ms 53920 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16840 KB Output is correct
2 Correct 224 ms 52412 KB Output is correct
3 Correct 231 ms 53920 KB Output is correct
4 Incorrect 54 ms 17148 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 41 ms 16696 KB Output is correct
2 Correct 265 ms 58936 KB Output is correct
3 Correct 281 ms 57952 KB Output is correct
4 Correct 238 ms 57916 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16696 KB Output is correct
2 Correct 265 ms 58936 KB Output is correct
3 Correct 281 ms 57952 KB Output is correct
4 Correct 238 ms 57916 KB Output is correct
5 Incorrect 41 ms 16564 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 58 ms 16740 KB Output is correct
2 Correct 244 ms 52432 KB Output is correct
3 Correct 222 ms 52560 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 16740 KB Output is correct
2 Correct 244 ms 52432 KB Output is correct
3 Correct 222 ms 52560 KB Output is correct
4 Incorrect 45 ms 17176 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 47 ms 16728 KB Output is correct
2 Correct 264 ms 58928 KB Output is correct
3 Correct 288 ms 57976 KB Output is correct
4 Correct 236 ms 57908 KB Output is correct
5 Correct 41 ms 16568 KB Output is correct
6 Correct 207 ms 51392 KB Output is correct
7 Correct 265 ms 51812 KB Output is correct
8 Correct 278 ms 55252 KB Output is correct
9 Correct 290 ms 55256 KB Output is correct
10 Correct 298 ms 59080 KB Output is correct
11 Correct 403 ms 58508 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16728 KB Output is correct
2 Correct 264 ms 58928 KB Output is correct
3 Correct 288 ms 57976 KB Output is correct
4 Correct 236 ms 57908 KB Output is correct
5 Correct 41 ms 16568 KB Output is correct
6 Correct 207 ms 51392 KB Output is correct
7 Correct 265 ms 51812 KB Output is correct
8 Correct 278 ms 55252 KB Output is correct
9 Correct 290 ms 55256 KB Output is correct
10 Correct 298 ms 59080 KB Output is correct
11 Correct 403 ms 58508 KB Output is correct
12 Incorrect 41 ms 17208 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 44 ms 16720 KB Output is correct
2 Correct 58 ms 18004 KB Output is correct
3 Correct 62 ms 18140 KB Output is correct
4 Correct 66 ms 18020 KB Output is correct
5 Correct 61 ms 18188 KB Output is correct
6 Correct 56 ms 17956 KB Output is correct
7 Correct 49 ms 16792 KB Output is correct
8 Correct 263 ms 52384 KB Output is correct
9 Correct 220 ms 53960 KB Output is correct
10 Correct 51 ms 17232 KB Output is correct
11 Correct 268 ms 61048 KB Output is correct
12 Correct 250 ms 61128 KB Output is correct
13 Correct 274 ms 60968 KB Output is correct
14 Correct 51 ms 17256 KB Output is correct
15 Correct 228 ms 54400 KB Output is correct
16 Correct 254 ms 54900 KB Output is correct
17 Correct 292 ms 55148 KB Output is correct
18 Correct 271 ms 55080 KB Output is correct
19 Correct 305 ms 59128 KB Output is correct
20 Correct 375 ms 58524 KB Output is correct
21 Correct 207 ms 54476 KB Output is correct
22 Correct 263 ms 54440 KB Output is correct
23 Correct 246 ms 54800 KB Output is correct
24 Correct 235 ms 54884 KB Output is correct
25 Correct 319 ms 57756 KB Output is correct
26 Correct 256 ms 54388 KB Output is correct
27 Correct 262 ms 54320 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16720 KB Output is correct
2 Correct 58 ms 18004 KB Output is correct
3 Correct 62 ms 18140 KB Output is correct
4 Correct 66 ms 18020 KB Output is correct
5 Correct 61 ms 18188 KB Output is correct
6 Correct 56 ms 17956 KB Output is correct
7 Correct 49 ms 16792 KB Output is correct
8 Correct 263 ms 52384 KB Output is correct
9 Correct 220 ms 53960 KB Output is correct
10 Correct 51 ms 17232 KB Output is correct
11 Correct 268 ms 61048 KB Output is correct
12 Correct 250 ms 61128 KB Output is correct
13 Correct 274 ms 60968 KB Output is correct
14 Correct 51 ms 17256 KB Output is correct
15 Correct 228 ms 54400 KB Output is correct
16 Correct 254 ms 54900 KB Output is correct
17 Correct 292 ms 55148 KB Output is correct
18 Correct 271 ms 55080 KB Output is correct
19 Correct 305 ms 59128 KB Output is correct
20 Correct 375 ms 58524 KB Output is correct
21 Correct 207 ms 54476 KB Output is correct
22 Correct 263 ms 54440 KB Output is correct
23 Correct 246 ms 54800 KB Output is correct
24 Correct 235 ms 54884 KB Output is correct
25 Correct 319 ms 57756 KB Output is correct
26 Correct 256 ms 54388 KB Output is correct
27 Correct 262 ms 54320 KB Output is correct
28 Incorrect 44 ms 17228 KB Extra information in the output file
29 Halted 0 ms 0 KB -