oj.uz

Submission #533003

# Submission time Handle Problem Language Result Execution time Memory
533003 2022-03-04T10:39:47 Z Sohsoh84 Inside information (BOI21_servers) C++17
2.5 / 100
 675 ms 149088 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 16788 KB Output is correct
2 Correct 65 ms 18552 KB Output is correct
3 Correct 60 ms 18632 KB Output is correct
4 Correct 72 ms 18640 KB Output is correct
5 Correct 80 ms 18328 KB Output is correct
6 Correct 78 ms 18088 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 16788 KB Output is correct
2 Correct 65 ms 18552 KB Output is correct
3 Correct 60 ms 18632 KB Output is correct
4 Correct 72 ms 18640 KB Output is correct
5 Correct 80 ms 18328 KB Output is correct
6 Correct 78 ms 18088 KB Output is correct
7 Incorrect 50 ms 16824 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16824 KB Output is correct
2 Runtime error 181 ms 114028 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16824 KB Output is correct
2 Runtime error 181 ms 114028 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 16744 KB Output is correct
2 Runtime error 228 ms 104824 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 16744 KB Output is correct
2 Runtime error 228 ms 104824 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16764 KB Output is correct
2 Correct 675 ms 149088 KB Output is correct
3 Runtime error 163 ms 92188 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16764 KB Output is correct
2 Correct 675 ms 149088 KB Output is correct
3 Runtime error 163 ms 92188 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 16692 KB Output is correct
2 Runtime error 258 ms 104836 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 16692 KB Output is correct
2 Runtime error 258 ms 104836 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16696 KB Output is correct
2 Correct 66 ms 18552 KB Output is correct
3 Correct 73 ms 18696 KB Output is correct
4 Correct 78 ms 18628 KB Output is correct
5 Correct 90 ms 18260 KB Output is correct
6 Correct 60 ms 18036 KB Output is correct
7 Correct 69 ms 16712 KB Output is correct
8 Runtime error 202 ms 114040 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16696 KB Output is correct
2 Correct 66 ms 18552 KB Output is correct
3 Correct 73 ms 18696 KB Output is correct
4 Correct 78 ms 18628 KB Output is correct
5 Correct 90 ms 18260 KB Output is correct
6 Correct 60 ms 18036 KB Output is correct
7 Correct 69 ms 16712 KB Output is correct
8 Runtime error 202 ms 114040 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -