oj.uz

Submission #533008

# Submission time Handle Problem Language Result Execution time Memory
533008 2022-03-04T10:51:12 Z Sohsoh84 Inside information (BOI21_servers) C++17
50 / 100
 515 ms 60304 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 48 ms 17332 KB Output is correct
2 Correct 58 ms 18732 KB Output is correct
3 Correct 70 ms 18772 KB Output is correct
4 Correct 77 ms 18752 KB Output is correct
5 Correct 64 ms 18952 KB Output is correct
6 Correct 58 ms 18736 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 17332 KB Output is correct
2 Correct 58 ms 18732 KB Output is correct
3 Correct 70 ms 18772 KB Output is correct
4 Correct 77 ms 18752 KB Output is correct
5 Correct 64 ms 18952 KB Output is correct
6 Correct 58 ms 18736 KB Output is correct
7 Incorrect 49 ms 17308 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 66 ms 17240 KB Output is correct
2 Correct 223 ms 53396 KB Output is correct
3 Correct 211 ms 51896 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 66 ms 17240 KB Output is correct
2 Correct 223 ms 53396 KB Output is correct
3 Correct 211 ms 51896 KB Output is correct
4 Incorrect 48 ms 17112 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 17208 KB Output is correct
2 Correct 346 ms 60304 KB Output is correct
3 Correct 351 ms 58772 KB Output is correct
4 Correct 359 ms 58692 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 17208 KB Output is correct
2 Correct 346 ms 60304 KB Output is correct
3 Correct 351 ms 58772 KB Output is correct
4 Correct 359 ms 58692 KB Output is correct
5 Incorrect 41 ms 17204 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 17152 KB Output is correct
2 Correct 257 ms 53784 KB Output is correct
3 Correct 283 ms 54264 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 17152 KB Output is correct
2 Correct 257 ms 53784 KB Output is correct
3 Correct 283 ms 54264 KB Output is correct
4 Incorrect 43 ms 17108 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 44 ms 17228 KB Output is correct
2 Correct 332 ms 60256 KB Output is correct
3 Correct 387 ms 58704 KB Output is correct
4 Correct 282 ms 58660 KB Output is correct
5 Correct 41 ms 17164 KB Output is correct
6 Correct 235 ms 52120 KB Output is correct
7 Correct 300 ms 52632 KB Output is correct
8 Correct 345 ms 52556 KB Output is correct
9 Correct 327 ms 52680 KB Output is correct
10 Correct 351 ms 56596 KB Output is correct
11 Correct 515 ms 56548 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 17228 KB Output is correct
2 Correct 332 ms 60256 KB Output is correct
3 Correct 387 ms 58704 KB Output is correct
4 Correct 282 ms 58660 KB Output is correct
5 Correct 41 ms 17164 KB Output is correct
6 Correct 235 ms 52120 KB Output is correct
7 Correct 300 ms 52632 KB Output is correct
8 Correct 345 ms 52556 KB Output is correct
9 Correct 327 ms 52680 KB Output is correct
10 Correct 351 ms 56596 KB Output is correct
11 Correct 515 ms 56548 KB Output is correct
12 Incorrect 41 ms 17064 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 43 ms 17236 KB Output is correct
2 Correct 56 ms 18656 KB Output is correct
3 Correct 60 ms 18952 KB Output is correct
4 Correct 65 ms 18780 KB Output is correct
5 Correct 62 ms 18984 KB Output is correct
6 Correct 54 ms 18776 KB Output is correct
7 Correct 43 ms 17204 KB Output is correct
8 Correct 217 ms 53384 KB Output is correct
9 Correct 218 ms 51924 KB Output is correct
10 Correct 43 ms 17084 KB Output is correct
11 Correct 341 ms 58572 KB Output is correct
12 Correct 322 ms 58496 KB Output is correct
13 Correct 278 ms 58424 KB Output is correct
14 Correct 50 ms 17016 KB Output is correct
15 Correct 268 ms 51828 KB Output is correct
16 Correct 270 ms 52396 KB Output is correct
17 Correct 353 ms 52616 KB Output is correct
18 Correct 300 ms 52600 KB Output is correct
19 Correct 357 ms 56604 KB Output is correct
20 Correct 446 ms 56492 KB Output is correct
21 Correct 223 ms 51956 KB Output is correct
22 Correct 213 ms 51876 KB Output is correct
23 Correct 279 ms 52424 KB Output is correct
24 Correct 276 ms 52368 KB Output is correct
25 Correct 436 ms 57072 KB Output is correct
26 Correct 296 ms 51724 KB Output is correct
27 Correct 281 ms 51660 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 17236 KB Output is correct
2 Correct 56 ms 18656 KB Output is correct
3 Correct 60 ms 18952 KB Output is correct
4 Correct 65 ms 18780 KB Output is correct
5 Correct 62 ms 18984 KB Output is correct
6 Correct 54 ms 18776 KB Output is correct
7 Correct 43 ms 17204 KB Output is correct
8 Correct 217 ms 53384 KB Output is correct
9 Correct 218 ms 51924 KB Output is correct
10 Correct 43 ms 17084 KB Output is correct
11 Correct 341 ms 58572 KB Output is correct
12 Correct 322 ms 58496 KB Output is correct
13 Correct 278 ms 58424 KB Output is correct
14 Correct 50 ms 17016 KB Output is correct
15 Correct 268 ms 51828 KB Output is correct
16 Correct 270 ms 52396 KB Output is correct
17 Correct 353 ms 52616 KB Output is correct
18 Correct 300 ms 52600 KB Output is correct
19 Correct 357 ms 56604 KB Output is correct
20 Correct 446 ms 56492 KB Output is correct
21 Correct 223 ms 51956 KB Output is correct
22 Correct 213 ms 51876 KB Output is correct
23 Correct 279 ms 52424 KB Output is correct
24 Correct 276 ms 52368 KB Output is correct
25 Correct 436 ms 57072 KB Output is correct
26 Correct 296 ms 51724 KB Output is correct
27 Correct 281 ms 51660 KB Output is correct
28 Incorrect 44 ms 17052 KB Extra information in the output file
29 Halted 0 ms 0 KB -