#include "bits/stdc++.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
struct edge {
int to, cost;
bool operator <(edge o) const {
return cost > o.cost;
}
};
const int MAXN = 3e5;
int tree[4 * MAXN];
void update(int x, int l, int r, int p, int v) {
if (l == r) {
tree[x] += v;
return;
}
int mid = (l + r) / 2;
if (p <= mid) update(2 * x, l, mid, p, v);
else update(2 * x + 1, mid + 1, r, p, v);
tree[x] = tree[2 * x] + tree[2 * x + 1];
}
int query(int x, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[x];
if (l > qr || ql > r) return 0;
int mid = (l + r) / 2;
return query(2 * x, l, mid, ql, qr) + query(2 * x + 1, mid + 1, r, ql, qr);
}
set<edge> adj[200005];
set<pair<int, int>> query_q[200005];
vector<int> query_c[200005];
int ans[300005];
int sz[200005];
void dfs_centroid(int node, int par = -1) {
sz[node] = 1;
for (auto nxt : adj[node]) {
if (nxt.to == par) continue;
dfs_centroid(nxt.to, node);
sz[node] += sz[nxt.to];
}
return;
}
int find_centroid(int node, int total, int par = -1) {
for (auto nxt : adj[node]) {
if (nxt.to == par) continue;
if (sz[nxt.to] > total / 2) return find_centroid(nxt.to, total, node);
}
return node;
}
vector<int> children;
map<int, int> L;
void dfs_one(int node, int par, int cost) {
auto itr = query_q[node].begin();
while (itr != query_q[node].end()) {
auto m_itr = L.find(itr->first);
if (m_itr == L.end() || m_itr->second > itr->second) {
itr++; continue;
}
ans[itr->second] = -1;
itr = query_q[node].erase(itr);
}
children.push_back(node);
for (auto nxt : adj[node]) {
if (nxt.to == par) continue;
if (nxt.cost < cost) dfs_one(nxt.to, node, cost);
}
}
vector<pair<int, int>> rev;
void dfs_two(int node, int par, int cost) {
L[node] = cost;
update(1, 1, MAXN, cost, 1);
rev.push_back({cost, -1});
for (auto nxt : adj[node]) {
if (nxt.to == par) continue;
if (nxt.cost > cost) dfs_two(nxt.to, node, cost);
}
}
void solve(int node) {
L.clear();
for (auto nxt : adj[node]) {
children.clear();
L[node] = nxt.cost;
dfs_one(nxt.to, node, nxt.cost);
for (auto child : children) {
for (auto q : query_c[child]) {
if (q > nxt.cost) {
ans[q] += query(1, 1, MAXN, 1, q) + 1;
}
}
}
dfs_two(nxt.to, node, nxt.cost);
}
auto itr = query_q[node].begin();
while (itr != query_q[node].end()) {
auto m_itr = L.find(itr->first);
if (m_itr == L.end() || m_itr->second > itr->second) {
itr++; continue;
}
ans[itr->second] = -1;
itr = query_q[node].erase(itr);
}
for (auto q : query_c[node]) {
ans[q] += query(1, 1, MAXN, 1, q) + 1;
}
while (!rev.empty()) {
update(1, 1, MAXN, rev.back().first, rev.back().second);
rev.pop_back();
}
}
void centroid(int node) {
dfs_centroid(node);
int cent = find_centroid(node, sz[node]);
solve(cent);
// clean up
vector<edge> del(adj[cent].begin(), adj[cent].end());
for (auto e : del) {
adj[cent].erase(e);
adj[e.to].erase(adj[e.to].find({cent, e.cost}));
centroid(e.to);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("", "r", stdin);
// freopen("", "w", stdout);
int n, k; cin >> n >> k;
fill(ans, ans+300005, -3);
for (int i = 1; i <= n + k -1; i++) {
char type; cin >> type;
if (type == 'S') {
int a, b; cin >> a >> b;
adj[a].insert({b, i});
adj[b].insert({a, i});
} else if (type == 'Q') {
int a, b; cin >> a >> b;
// if b can reach a
query_q[b].insert({a, i});
ans[i] = -2;
} else {
// type c
int d; cin >> d;
query_c[d].push_back(i);
ans[i] = 0;
}
}
centroid(1);
for (int i = 1; i <= n + k - 1; i++) {
if (ans[i] == -3) continue;
if (ans[i] >= 0) {
cout << ans[i];
} else {
cout << (ans[i] == -1 ? "yes" : "no");
}
cout << "\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
58 ms |
32376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
58 ms |
32376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
59 ms |
32464 KB |
Output is correct |
| 2 |
Incorrect |
355 ms |
54040 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
59 ms |
32464 KB |
Output is correct |
| 2 |
Incorrect |
355 ms |
54040 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
52 ms |
32448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
52 ms |
32448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
78 ms |
32484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
78 ms |
32484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
66 ms |
32400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
66 ms |
32400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
66 ms |
32488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
66 ms |
32488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
