oj.uz

답안 #912648

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
912648 2024-01-19T17:15:26 Z MinaRagy06 Inside information (BOI21_servers) C++17
0 / 100
 48 ms 47004 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef int64_t ll;
#define SZ(x) (int) x.size()

const int N = 120'005, LOG = 18, B = 700;
vector<array<int, 3>> adj[N];
vector<int> dp[N];
int lst;
int solve(int i, int par) {
	if (~dp[i][par]) return dp[i][par];
	int j = (par == SZ(adj[i])? 0 : par + 1);
	dp[i][par] = 1;
	if (j < SZ(adj[i])) {
		if (adj[i][j][1] > lst) return dp[i][par];
		dp[i][par] += solve(adj[i][j][0], adj[i][j][2]) + solve(i, j) - 1;
	}
	return dp[i][par];
}
int st[N], en[N], sz[N], curt;
array<int, 2> par[N];
bool isanc(int u, int v) {
	return st[u] <= st[v] && en[v] <= en[u];
}
struct sparse {
	array<int, 2> a[2 * N][LOG + 1];
	int n;
	int logs[2 * N];
	void build(int _n) {
		n = _n;
		logs[1] = 0;
		for (int j = 2; j <= n; j++) {
			logs[j] = logs[j >> 1] + 1;
		}
		for (int j = 1; j <= LOG; j++) {
			for (int i = 0; i + (1 << (j - 1)) < n; i++) {
				a[i][j] = min(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
			}
		}
	}
	int query(int u, int v) {
		if (st[u] > st[v]) swap(u, v);
		if (isanc(u, v)) {
			return u;
		}
		int l = en[u], r = st[v];
		int lg = logs[r - l + 1];
		array<int, 2> mn = min(a[l][lg], a[r - (1 << lg) + 1][lg]);
		return mn[1];
	}
} lca;
void dfs(int i, int h, int p, int part) {
	lca.a[curt][0] = {h, i};
	st[i] = curt++;
	sz[i] = 1;
	par[i] = {p, part};
	for (int j = 0; j < SZ(adj[i]); j++) {
		auto [nxt, t, nxtidx] = adj[i][j];
		if (nxt == p) {
			swap(adj[i][j], adj[i][SZ(adj[i]) - 1]);
			if (j != SZ(adj[i]) - 1) j--;
			continue;
		}
		dfs(nxt, h + 1, i, t);
		sz[i] += sz[nxt];
		if (sz[nxt] > sz[adj[i][0][0]]) swap(adj[i][0], adj[i][j]);
		lca.a[curt][0] = {h, i};
		curt++;
	}
	en[i] = curt - 1;
}
vector<array<int, 4>> ask[N];
int ans[N];
void process(int i, int p) {
	for (auto [a, b, t, idx] : ask[i]) {
		int cur = a, lst1 = -1e9;
		bool ok = 1;
		while (cur != i) {
			ok &= lst1 < par[cur][1];
			lst1 = par[cur][1];
			cur = par[cur][0];
		}
		cur = b;
		int lst2 = 1e9;
		while (cur != i) {
			ok &= par[cur][1] < lst2;
			lst2 = par[cur][1];
			cur = par[cur][0];
		}
		ok &= lst1 < lst2;
		if (b != i) {
			ok &= par[b][1] <= t;
		} else if (a != i) {
			ok &= lst1 <= t;
		}
		ans[idx] += ok;
	}
	for (auto [nxt, t, nxtidx] : adj[i]) {
		if (nxt == p) continue;
		process(nxt, i);
	}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, q;
	cin >> n >> q;
	q += n - 1;
	pair<char, vector<int>> v[q];
	for (int i = 0; i < q; i++) {
		cin >> v[i].first;
		if (v[i].first == 'S') {
			int a, b;
			cin >> a >> b;
			int x = adj[b].size(), y = adj[a].size();
			adj[a].push_back({b, i, x});
			adj[b].push_back({a, i, y});
			v[i].second = {a, b};
		} else if (v[i].first == 'Q') {
			int a, b;
			cin >> a >> b;
			v[i].second = {a, b};
		} else {
			int a;
			cin >> a;
			v[i].second = {a};
		}
	}
	dfs(1, 0, 1, 0);
	lca.build(curt);
	for (int i = 1; i <= n; i++) {
		dp[i].resize(adj[i].size() + 1);
		for (int j = 0; j <= SZ(adj[i]); j++) {
			dp[i][j] = -1;
		}
	}
	vector<array<int, 3>> upd;
	lst = -1;
	for (int i = 0; i < q; i++) {
		if (upd.size() == B) {
			lst = i - 1;
			upd.clear();
			for (int j = 1; j <= n; j++) {
				for (int k = 0; k <= SZ(adj[j]); k++) {
					dp[j][k] = -1;
				}
			}
		}
		if (v[i].first == 'S') {
			int a = v[i].second[0], b = v[i].second[1];
			if (isanc(b, a)) swap(a, b);
			upd.push_back({a, b, i});
		} else if (v[i].first == 'Q') {
			int a = v[i].second[0], b = v[i].second[1];
			int mid = lca.query(a, b);
			ask[mid].push_back({b, a, i, i});
		} else {
			int x = v[i].second[0];
			ans[i] += solve(x, adj[x].size());
			for (auto [a, b, t] : upd) {
				if (isanc(b, x)) {
					ask[b].push_back({x, b, t - 1, i});
				} else if (isanc(a, x)) {
					ask[a].push_back({x, a, t - 1, i});
				} else {
					int mid = lca.query(a, x);
					ask[mid].push_back({x, a, t - 1, i});
				}
			}
		}
	}
	process(1, 1);
	for (int i = 0; i < q; i++) {
		if (v[i].first == 'Q') {
			cout << (ans[i]? "yes\n" : "no\n");
		} else if (v[i].first == 'C') {
			cout << ans[i] << '\n';
		}
	}
	return 0;
}

Subtask #1
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 24524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 24524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Runtime error 47 ms 47004 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Runtime error 47 ms 47004 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 24756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 24756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 24268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 24268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 24704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 24704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 24724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 24724 KB Output isn't correct
2 Halted 0 ms 0 KB -