oj.uz

답안 #533011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
533011 2022-03-04T10:54:38 Z Sohsoh84 Inside information (BOI21_servers) C++17
50 / 100
 1150 ms 171032 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;

	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

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 38196 KB Output is correct
2 Correct 79 ms 40096 KB Output is correct
3 Correct 73 ms 40228 KB Output is correct
4 Correct 91 ms 40128 KB Output is correct
5 Correct 97 ms 39784 KB Output is correct
6 Correct 88 ms 39604 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 38196 KB Output is correct
2 Correct 79 ms 40096 KB Output is correct
3 Correct 73 ms 40228 KB Output is correct
4 Correct 91 ms 40128 KB Output is correct
5 Correct 97 ms 39784 KB Output is correct
6 Correct 88 ms 39604 KB Output is correct
7 Incorrect 66 ms 38220 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 38188 KB Output is correct
2 Correct 323 ms 86592 KB Output is correct
3 Correct 383 ms 86608 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 38188 KB Output is correct
2 Correct 323 ms 86592 KB Output is correct
3 Correct 383 ms 86608 KB Output is correct
4 Incorrect 67 ms 38324 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 38192 KB Output is correct
2 Correct 489 ms 96340 KB Output is correct
3 Correct 468 ms 96352 KB Output is correct
4 Correct 710 ms 170528 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 38192 KB Output is correct
2 Correct 489 ms 96340 KB Output is correct
3 Correct 468 ms 96352 KB Output is correct
4 Correct 710 ms 170528 KB Output is correct
5 Incorrect 71 ms 38368 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 38340 KB Output is correct
2 Correct 761 ms 159100 KB Output is correct
3 Correct 434 ms 94576 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 38340 KB Output is correct
2 Correct 761 ms 159100 KB Output is correct
3 Correct 434 ms 94576 KB Output is correct
4 Incorrect 63 ms 38424 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 38312 KB Output is correct
2 Correct 504 ms 96656 KB Output is correct
3 Correct 494 ms 96756 KB Output is correct
4 Correct 694 ms 171032 KB Output is correct
5 Correct 68 ms 38312 KB Output is correct
6 Correct 785 ms 159212 KB Output is correct
7 Correct 408 ms 94544 KB Output is correct
8 Correct 589 ms 92808 KB Output is correct
9 Correct 479 ms 93280 KB Output is correct
10 Correct 1065 ms 147544 KB Output is correct
11 Correct 1135 ms 147068 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 38312 KB Output is correct
2 Correct 504 ms 96656 KB Output is correct
3 Correct 494 ms 96756 KB Output is correct
4 Correct 694 ms 171032 KB Output is correct
5 Correct 68 ms 38312 KB Output is correct
6 Correct 785 ms 159212 KB Output is correct
7 Correct 408 ms 94544 KB Output is correct
8 Correct 589 ms 92808 KB Output is correct
9 Correct 479 ms 93280 KB Output is correct
10 Correct 1065 ms 147544 KB Output is correct
11 Correct 1135 ms 147068 KB Output is correct
12 Incorrect 64 ms 38480 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 38340 KB Output is correct
2 Correct 72 ms 40108 KB Output is correct
3 Correct 71 ms 40252 KB Output is correct
4 Correct 91 ms 40260 KB Output is correct
5 Correct 100 ms 39924 KB Output is correct
6 Correct 75 ms 39688 KB Output is correct
7 Correct 57 ms 38352 KB Output is correct
8 Correct 341 ms 86960 KB Output is correct
9 Correct 371 ms 86984 KB Output is correct
10 Correct 55 ms 38496 KB Output is correct
11 Correct 466 ms 96796 KB Output is correct
12 Correct 475 ms 96628 KB Output is correct
13 Correct 677 ms 170688 KB Output is correct
14 Correct 61 ms 38496 KB Output is correct
15 Correct 768 ms 158772 KB Output is correct
16 Correct 443 ms 94104 KB Output is correct
17 Correct 503 ms 92460 KB Output is correct
18 Correct 454 ms 92828 KB Output is correct
19 Correct 1040 ms 147068 KB Output is correct
20 Correct 1150 ms 146836 KB Output is correct
21 Correct 343 ms 89332 KB Output is correct
22 Correct 397 ms 90140 KB Output is correct
23 Correct 403 ms 93164 KB Output is correct
24 Correct 435 ms 93340 KB Output is correct
25 Correct 617 ms 97988 KB Output is correct
26 Correct 670 ms 116392 KB Output is correct
27 Correct 701 ms 121480 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 38340 KB Output is correct
2 Correct 72 ms 40108 KB Output is correct
3 Correct 71 ms 40252 KB Output is correct
4 Correct 91 ms 40260 KB Output is correct
5 Correct 100 ms 39924 KB Output is correct
6 Correct 75 ms 39688 KB Output is correct
7 Correct 57 ms 38352 KB Output is correct
8 Correct 341 ms 86960 KB Output is correct
9 Correct 371 ms 86984 KB Output is correct
10 Correct 55 ms 38496 KB Output is correct
11 Correct 466 ms 96796 KB Output is correct
12 Correct 475 ms 96628 KB Output is correct
13 Correct 677 ms 170688 KB Output is correct
14 Correct 61 ms 38496 KB Output is correct
15 Correct 768 ms 158772 KB Output is correct
16 Correct 443 ms 94104 KB Output is correct
17 Correct 503 ms 92460 KB Output is correct
18 Correct 454 ms 92828 KB Output is correct
19 Correct 1040 ms 147068 KB Output is correct
20 Correct 1150 ms 146836 KB Output is correct
21 Correct 343 ms 89332 KB Output is correct
22 Correct 397 ms 90140 KB Output is correct
23 Correct 403 ms 93164 KB Output is correct
24 Correct 435 ms 93340 KB Output is correct
25 Correct 617 ms 97988 KB Output is correct
26 Correct 670 ms 116392 KB Output is correct
27 Correct 701 ms 121480 KB Output is correct
28 Incorrect 59 ms 38444 KB Extra information in the output file
29 Halted 0 ms 0 KB -