oj.uz

답안 #528290

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
528290 2022-02-19T19:50:10 Z iliaM Inside information (BOI21_servers) C++17
0 / 100
 44 ms 28100 KB 
#include <bits/stdc++.h>
using namespace std;
#define cerr cerr << "DEBUG "

constexpr int N = 24e4 + 10;

int n, k;
vector<pair<int, int>> qp[N];
vector<int> qu[N];
vector<pair<int, int>> up, down;
pair<int, int> tmp[N]; 
vector<pair<int, pair<int, int>>> pairs;
vector<int> verts;
bool mark[N];
int sz[N];
vector<pair<int, int>> g[N];
bool used[N];
long long ans[N];
int parent[N];

int centroid(int v, int p, int m) {
	tmp[v] = make_pair(INT_MAX, INT_MAX);
	verts.push_back(v);
	mark[v] = true;

	int ret = 0, cool = 1;
	sz[v] = 1;
	for (auto &e : g[v]) {
		int u = e.first;
		if (u != p && !used[u]) {
			ret ^= ~centroid(u, v, m);
			cool &= sz[u] <= m / 2;
			sz[v] += sz[u];
		}
	}
	//cerr << cool << '\n';
	return cool && m - sz[v] <= m / 2 ? v : ~ret;
}


void dfs(int v, int p, int fe, int f, int s) {
	//cerr << "DFSING: " << v << '\n';
	sz[v] = 1;
	parent[v] = fe;
	if (~f) {
		for (auto &query : qu[v]) {
			up.push_back({fe, query});
		}
		for (auto &query : qp[v]) {
			pairs.push_back({query.first, {fe, query.second}});
		}
	}
	if (~s) {
		down.push_back({fe, s});
		tmp[v] = make_pair(fe, s);
	}
	for (auto &e : g[v]) {
		int u = e.first, w = e.second;
		if (u != p && !used[u]) {
			dfs(u, v, fe, w < f ? w : -1, w > s ? w : -1);
			sz[v] += sz[u];
		}
	}
	//cerr << "UNDFSING: " << v << ' ' << sz[v] << '\n';
}

int fen[N];

void update(int i, int x) {
	for (++i; i < N; i += i & -i) {
		fen[i] += x;
	}
}

int query(int i) {
	int ret = 0;
	for (++i; i > 0; i -= i & -i) {
		ret += fen[i];
	}
	return ret;
}

void solve() {
	static vector<int> vec[N];
	auto &a = up, &b = down;
	for (int i = 0; i < (int) b.size(); ++i) {
		vec[i].clear();
	}

	for (auto &x : a) {
		auto p = upper_bound(b.begin(), b.end(), make_pair(x.first, INT_MAX));
		ans[x.second]++; // for centroid
		if (p != b.end()) {
			vec[p - b.begin()].push_back(x.second);
		}
	}

	for (int i = (int) b.size() - 1; i >= 0; --i) {
		update(b[i].second, +1);
		for (auto &x : vec[i]) {
			ans[x] += query(x);
		}
	}
	for (auto &x : b) {
		update(x.first, -1);
	}
}

void decompose(int v, int m) {
	int cent = centroid(v, -1, m);
	
	//cerr << v << ' ' << cent << ' ' << m << '\n';

	up.clear();
	down.clear();
	pairs.clear();

	/*for (int i = 0; i < n; ++i) {
		cout << sz[i] << ' ';
	}
	cout << '\n';*/
	for (auto &e : g[cent]) {
		int u = e.first, w = e.second;
		if (!used[u]) {
			//cerr << u << '\n';
			dfs(u, cent, w, w, w);
		}
	}
	/*for (int i = 0; i < n; ++i) {
		cout << sz[i] << ' ';
	}
	cout << '\n';*/
	
	// calc for pairs in subtrees
	sort(down.begin(), down.end());
	solve();
	for (auto &pr : pairs) {
		int x = pr.first;
		if (parent[x] == pr.second.first) {
			continue;
		}
		if (x == cent) {
			ans[pr.second.second] = 1;
		} else if (mark[x]) {
			bool ok = pr.second.first < tmp[x].first && tmp[x].second < pr.second.second;
			ans[pr.second.second] = ok;
		}
	}

	// calc for pairs from centroid
	for (auto &query : qp[cent]) {
		if (mark[query.first]) {
			ans[query.second] = query.first == cent || tmp[query.first].second < query.second;
		}
	}
	for (auto &query : qu[cent]) {
		ans[query] += 1 + down.size();
	}

	for (auto &v : verts) {
		mark[v] = false;
	}
	used[cent] = true;
	for (auto &e : g[cent]) {
		int u = e.first;
		if (!used[u]) {
			//cerr << "DOING: " << u << ' ' << sz[u] << '\n';
			decompose(u, sz[u]);
		}
	}
}

int qtype[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
		
	cin >> n >> k;
	for (int i = 0; i < n + k - 1; ++i) {
		char op;
		cin >> op;
		int v;
		cin >> v;
		--v;
		if (op == 'S') {
			int u;
			cin >> u;
			--u;
			g[v].push_back({u, i});
			g[u].push_back({v, i});
		} else if (op == 'Q') {
			qtype[i] = 1;
			int u;
			cin >> u;
			--u;
			qp[u].push_back({v, i});
		} else {
			qtype[i] = 2;
			qu[v].push_back(i);
		}
	}

	decompose(0, n);
	
	for (int i = 0; i < n + k - 1; ++i) {
		if (qtype[i] == 1) {
			cout << (ans[i] ? "yes" : "no") << '\n';
		} else if (qtype[i] == 2) {
			cout << ans[i] << '\n';
		}
	}
}

Subtask #1
0 / 2.5

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

Subtask #2
0 / 2.5

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

Subtask #3
0 / 2.5

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

Subtask #4
0 / 2.5

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

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

Subtask #12
0 / 17.5

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