이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2","popcnt","sse4","abm")
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef array<int, 4> p4i;
const int MXN = 120005, LG = 17;
int n, q;
vector<pii> edge[MXN];
vector<pii> qc[MXN];
vector<p4i> qq;
int ans[MXN * 2];
int d[MXN];
int p[LG][MXN], big[LG][MXN], lst[LG][MXN];
bitset<MXN> isP[LG], isN[LG];
void DFS(int id, int par, int dep) {
p[0][id] = par;
d[id] = dep;
for (auto &[e, i] : edge[id]) {
if (i == par) continue;
big[0][i] = e;
lst[0][i] = e;
DFS(i, id, dep + 1);
}
}
void MAKE_TREE() {
DFS(1, 1, 0);
isP[0].set();
isN[0].set();
FOR(w, 1, LG) {
FOR(i, 1, n + 1) {
int pp = p[w - 1][i];
p[w][i] = p[w - 1][pp];
big[w][i] = max(big[w - 1][i], big[w - 1][pp]);
lst[w][i] = lst[w - 1][pp];
isP[w][i] = (isP[w - 1][i]) & (isP[w - 1][pp]) & (lst[w - 1][i] < lst[0][pp]);
isN[w][i] = (isN[w - 1][i]) & (isN[w - 1][pp]) & (lst[w - 1][i] > lst[0][pp]);
}
}
}
namespace NSBL {
int JUMP(int x, int k) {
FOR(w, 0, LG) if (k & (1 << w)) x = p[w][x];
return x;
}
int LCA(int x, int y) {
if (d[x] < d[y]) swap(x, y);
x = JUMP(x, d[x] - d[y]);
if (x == y) return x;
for (int w = LG - 1; w >= 0; w--) {
if (p[w][x] == p[w][y]) continue;
x = p[w][x];
y = p[w][y];
}
return p[0][x];
}
int GET_BIG(int x, int k) {
int ans = INT_MIN;
FOR(w, 0, LG) if (k & (1 << w)) {
ans = max(ans, big[w][x]);
x = p[w][x];
}
return ans;
}
bool PS(int x, int k) {
int L = lst[0][x];
x = p[0][x];
k--;
FOR(w, 0, LG) if (k & (1 << w)) {
if (L > lst[0][x] || !isP[w][x]) return false;
L = lst[w][x];
x = p[w][x];
}
return true;
}
bool NG(int x, int k) {
int L = lst[0][x];
x = p[0][x];
k--;
FOR(w, 0, LG) if (k & (1 << w)) {
if (L < lst[0][x] || !isN[w][x]) return false;
L = lst[w][x];
x = p[w][x];
}
return true;
}
bool calc(int u, int v, int t) {
if (u == v) return true;
int lca = LCA(u, v);
int b = max(GET_BIG(u, d[u] - d[lca]), GET_BIG(v, d[v] - d[lca]));
// debug(u, v, lca, b);
if (b > t) return false;
if (lca == u) {
return NG(v, d[v] - d[u]);
} else if (lca == v) {
return PS(u, d[u] - d[v]);
} else {
int su = JUMP(u, d[u] - d[lca] - 1), sv = JUMP(v, d[v] - d[lca] - 1);
return NG(v, d[v] - d[lca]) && PS(u, d[u] - d[lca]) && (lst[0][su] < lst[0][sv]);
}
return false;
}
void DO() {
for (auto [u, v, t, aid] : qq) {
ans[aid] = (calc(v, u, t) ? -2 : -3);
}
}
}
namespace NSCD {
struct BIT {
int val[MXN];
vector<int> st;
void reset() {
for (auto &i : st) val[i] = 0;
st.clear();
}
void modify(int id, int v) {
for (; id <= n; id += (id & -id)) {
st.push_back(id);
val[id] += v;
}
}
int query(int id) {
int ans = 0;
for (; id > 0; id -= (id & -id)) ans += val[id];
return ans;
}
} B;
int sz[MXN];
bitset<MXN> ban;
void GET_SZ(int id, int par) {
sz[id] = 1;
for (auto &[e, i] : edge[id]) {
if (i == par) continue;
if (ban[i]) continue;
GET_SZ(i, id);
sz[id] += sz[i];
}
}
int GET_CT(int id, int par, int SZ) {
for (auto &[e, i] : edge[id]) {
if (i == par) continue;
if (ban[i]) continue;
if (sz[i] > SZ / 2) return GET_CT(i, id, SZ);
}
return id;
}
vector<pii> BFS_A(int sr, int w) {
vector<pii> ans;
ans.push_back(mp(w, sr));
for (int j = 0; j < ans.size(); j++) {
auto [L, id] = ans[j];
for (auto &[e, i] : edge[id]) {
if (ban[i]) continue;
if (L <= e) continue;
ans.push_back(mp(e, i));
}
}
return ans;
}
vector<pii> BFS_B(int sr, int w) {
vector<pii> ans;
ans.push_back(mp(w, sr));
for (int j = 0; j < ans.size(); j++) {
auto [L, id] = ans[j];
for (auto &[e, i] : edge[id]) {
if (ban[i]) continue;
if (L >= e) continue;
ans.push_back(mp(e, i));
}
}
return ans;
}
void CD(int id) {
GET_SZ(id, 0);
int ct = GET_CT(id, 0, sz[id]);
debug(id, ct);
sort(edge[ct].begin(), edge[ct].end(), greater<pii>());
B.reset();
for (auto [e, i] : edge[ct]) {
if (ban[i]) continue;
B.modify(e, 1);
vector<pii> a = BFS_A(i, e);
// cout << "a: ";
// for (auto &i : a) cout << i.sc << ' ';
// cout << endl;
for (auto [_, id] : a) {
for (auto [t, aid] : qc[id]) {
ans[aid] += B.query(t);
}
}
vector<pii> b = BFS_B(i, e);
// cout << "b: ";
// for (auto &i : b) cout << '<' << i.fs << ' ' << i.sc << '>' << ' ';
// cout << endl;
for (auto [t, id] : b) B.modify(t, 1);
B.modify(e, -1);
}
for (auto [t, aid] : qc[ct]) {
ans[aid] += B.query(t) + 1;
}
// FOR(i, 1, n + 1) cout << ans[7 + i] << ' ';
// cout << '\n';
ban[ct] = true;
for (auto [e, i] : edge[ct]) {
if (ban[i]) continue;
CD(i);
}
}
void DO() {
CD(1);
}
}
void miku() {
cin >> n >> q;
int ec = 0;
FOR(i, 0, q + n - 1) {
char c;
int a, b;
cin >> c;
if (c == 'S') {
cin >> a >> b;
ec++;
edge[a].push_back(mp(ec, b));
edge[b].push_back(mp(ec, a));
ans[i] = -1;
} else if (c == 'Q') {
cin >> a >> b;
qq.push_back({a, b, ec, i});
} else {
cin >> a;
qc[a].push_back(mp(ec, i));
}
}
MAKE_TREE();
NSBL::DO();
NSCD::DO();
FOR(i, 0, q + n - 1) {
if (ans[i] == -1) continue;
else if (ans[i] < 0) cout << (ans[i] == -2 ? "yes" : "no") << '\n';
else cout << ans[i] << '\n';
}
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
servers.cpp: In function 'std::vector<std::pair<int, int> > NSCD::BFS_A(int, int)':
servers.cpp:183:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
183 | for (int j = 0; j < ans.size(); j++) {
| ~~^~~~~~~~~~~~
servers.cpp: In function 'std::vector<std::pair<int, int> > NSCD::BFS_B(int, int)':
servers.cpp:197:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
197 | for (int j = 0; j < ans.size(); j++) {
| ~~^~~~~~~~~~~~
servers.cpp: In function 'void NSCD::CD(int)':
servers.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
servers.cpp:211:9: note: in expansion of macro 'debug'
211 | debug(id, ct);
| ^~~~~
# | 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... |
# | 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... |