이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cmath>
#include <algorithm>
#include <stack>
#include <bitset>
#include <numeric>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
using ull = unsigned long long;
using std::vector;
using std::pair;
using std::function;
using std::ios;
using std::cin;
using std::cout;
const int _ = 120007;
int N;
char opt[_];
int x[_], y[_], t[_], ans[_], siz[_], sprt[_], pw[_];
bool vis[_], inc[_], dec[_];
vector<pair<int, int>> G[_];
vector<int> sub[_];
int fw[_];
void ch(int k, int x) { for (; k <= N; k += k & -k) fw[k] += x; }
int qry(int k) { int ret = 0; for (; k; k &= k - 1) ret += fw[k]; return ret; }
void solve(int rt, const vector<int>& query) {
function<void(int, int)> dfs = [&](int u, int p) {
siz[u] = 1;
for (auto [v, w] : G[u]) if (!vis[v] && v != p) {
dfs(v, u); siz[u] += siz[v];
}
};
dfs(rt, 0);
function<int(int)> cent = [&](int u) {
for (auto [v, w] : G[u]) if (!vis[v] && siz[v] < siz[u] && siz[v] * 2 >= siz[rt])
return cent(v);
return u;
};
vis[rt = cent(rt)] = true;
inc[rt] = dec[rt] = true; sprt[rt] = 0;
vector<pair<int, int>> pt;
function<void(int, int)> dfs2 = [&](int u, int p) {
if (dec[u]) pt.emplace_back(pw[sprt[u]], -pw[u]);
for (auto [v, w] : G[u]) if (!vis[v] && v != p) {
sprt[v] = sprt[u]; pw[v] = w;
inc[v] = inc[u] && w < pw[u];
dec[v] = dec[u] && w > pw[u];
dfs2(v, u);
}
};
for (auto [v, w] : G[rt]) if (!vis[v]) {
sprt[v] = v; pw[v] = w; inc[v] = dec[v] = true;
dfs2(v, rt);
}
for (int i : query)
if (opt[i] == 'Q') {
if (sprt[x[i]] && sprt[y[i]] && sprt[x[i]] == sprt[y[i]]) {
sub[sprt[x[i]]].push_back(i);
continue;
}
if (!inc[x[i]] || !dec[y[i]]) { ans[i] = 0; continue; }
if (sprt[x[i]] && sprt[y[i]] && pw[sprt[x[i]]] > pw[sprt[y[i]]]) ans[i] = 0;
int lst = pw[y[i]]; if (!lst) lst = pw[sprt[x[i]]];
ans[i] &= lst <= t[i];
} else {
if (!inc[x[i]]) {
if (x[i] != rt) sub[sprt[x[i]]].push_back(i);
continue;
}
if (x[i] != rt) {
int sp = sprt[x[i]];
pt.emplace_back(pw[sp], i);
ans[i] += pw[sp] <= t[i];
sub[sp].push_back(i);
} else {
pt.emplace_back(0, i);
++ans[i];
}
}
sort(pt.begin(), pt.end(), std::greater<pair<int, int>>());
for (auto [i, j] : pt) {
if (j < 0) ch(-j, 1);
else ans[j] += qry(t[j]);
}
for (auto [i, j] : pt) if (j < 0) ch(-j, -1);
for (auto [v, w] : G[rt]) if (!vis[v]) {
vector<int> tmp; swap(tmp, sub[v]);
solve(v, tmp);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int K; cin >> N >> K;
int clo = 0, cnt = 0;
for (int rep = 0; rep != N + K - 1; ++rep) {
char o; int u, v; cin >> o >> u;
if (o == 'S') {
cin >> v; ++clo;
G[u].emplace_back(v, clo);
G[v].emplace_back(u, clo);
} else {
++cnt;
if (o == 'Q') { cin >> v; std::swap(u, v); ans[cnt] = 1; }
opt[cnt] = o; x[cnt] = u; y[cnt] = v; t[cnt] = clo;
}
}
vector<int> all(K); iota(all.begin(), all.end(), 1);
solve(1, all);
for (int i = 1; i <= K; ++i)
if (opt[i] == 'Q') cout << (ans[i] ? "yes\n" : "no\n");
else cout << ans[i] << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |