이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <algorithm>
#include <bitset>
#include <vector>
using namespace std;
struct way {
int mnt = -177013;
int mxt = -177013;
bool incr = true;
bool dcr = true;
way() {}
way(int t): mnt(t), mxt(t) {}
way reverse() {
way ans;
ans.mnt = mnt;
ans.mxt = mxt;
ans.dcr = incr;
ans.incr = dcr;
return ans;
}
way operator+(way w) {
if (mnt == -177013)
return w;
if (w.mnt == -177013)
return *this;
way ans;
ans.mnt = min(mnt, w.mnt);
ans.mxt = max(mxt, w.mxt);
ans.incr = (incr && w.incr && mxt <= w.mnt);
ans.dcr = (dcr && w.dcr && mnt >= w.mxt);
return ans;
}
friend ostream& operator<<(ostream& o, way w) {
o << "[" << w.incr << ' ' << w.dcr << ' ' << w.mnt << ' ' << w.mxt << "]";
return o;
}
};
const int MAXN = 120008;
vector<pair<int, int>> edg[MAXN];
int depth[MAXN];
pair<int, int> rt[MAXN];
pair<int, way> crt[MAXN];
void dfs(int v) {
auto [rtv, tmv] = rt[v];
int par = crt[rtv].first;
int parpar = crt[par].first;
if (depth[rtv] - depth[par] == depth[par] - depth[parpar]) {
crt[v] = {parpar, way(tmv) + crt[rtv].second + crt[par].second};
} else {
crt[v] = {rtv, way(tmv)};
}
for (auto [u, t] : edg[v]) {
if (u == rtv)
continue;
rt[u] = {v, t};
depth[u] = depth[v] + 1;
dfs(u);
}
}
pair<int, way> lift(int v, int d) {
way ans = rt[v].second;
while (d) {
if (depth[v] - depth[crt[v].first] <= d) {
ans = ans + crt[v].second;
d -= depth[v] - depth[crt[v].first];
v = crt[v].first;
} else {
ans = ans + rt[v].second;
--d;
v = rt[v].first;
}
}
return {v, ans};
}
pair<int, pair<way, way>> lca(int v, int u) {
way ansv = -177013;
way ansu = -177013;
if (depth[v] > depth[u]) {
pair<int, way> vlift = lift(v, depth[v] - depth[u]);
ansv = ansv + vlift.second;
v = vlift.first;
} else if (depth[v] < depth[u]) {
pair<int, way> ulift = lift(u, depth[u] - depth[v]);
ansu = ansu + ulift.second;
u = ulift.first;
}
while (u != v) {
if (crt[v].first != crt[u].first) {
ansv = ansv + crt[v].second;
ansu = ansu + crt[u].second;
v = crt[v].first;
u = crt[u].first;
} else {
ansv = ansv + rt[v].second;
ansu = ansu + rt[u].second;
v = rt[v].first;
u = rt[u].first;
}
}
return {v, {ansv, ansu}};
}
way get_way(int v, int u) {
auto ans = lca(v, u);
return ans.second.first + ans.second.second.reverse();
}
int centrt[MAXN];
int sz[MAXN];
bitset<MAXN> used;
vector<pair<int, int>> ways[MAXN];
void sz_dfs(int v, int rtv) {
sz[v] = 1;
for (auto [u, t] : edg[v]) {
if (u == rtv || used[u])
continue;
sz_dfs(u, v);
sz[v] += sz[u];
}
}
int centr_dfs(int v, int sz0) {
for (auto [u, t] : edg[v]) {
if (sz[u] > sz[v] || used[u])
continue;
if (sz[u] * 2 > sz0)
return centr_dfs(u, sz0);
}
return v;
}
void centrinit_dfs(int v, int rtv, int grt, way w, vector<pair<int, int>>& remilia) {
if (w.incr)
remilia.push_back({w.mnt, w.mxt});
centrt[v] = grt;
for (auto [u, t] : edg[v]) {
if (used[u] || u == rtv)
continue;
centrinit_dfs(u, v, grt, w + t, remilia);
}
}
void centr_decompose(int v) {
sz_dfs(v, -1);
v = centr_dfs(v, sz[v]);
//cout << v << endl;
used[v] = 1;
for (auto [u, t] : edg[v]) {
if (used[u])
continue;
centrinit_dfs(u, v, v, t, ways[v]);
centr_decompose(u);
}
}
vector<pair<pair<int, int>, int>> subqr[MAXN];
int ans_qr2(int v, int qrnum, int mxt) {
int ans = 0;
int u = v;
while (u > -1) {
//cout << "(" << u << ' ' << v << ") ";
way w = get_way(v, u);
if (w.incr && w.mxt <= mxt) {
//cout << u << ' ' << v << ": ";
//cout << "{" << w.mnt << ' ' << w.mxt << "} ";
++ans;
subqr[u].push_back({{w.mxt + 1, mxt}, qrnum});
//for (auto [mnt0, mxt0] : ways[u]) {
//if (mnt0 > w.mxt && mxt0 <= mxt) {
//cout << "(" << mnt0 << ' ' << mxt0 << ") ";
//++ans;
//} else {
//cout << "[" << mnt0 << ' ' << mxt0 << "] ";
//}
//}
//cout << endl;
}
u = centrt[u];
}
return ans;
}
struct fenwick {
void resize(int n) {
t.resize(n);
}
void add(int i, int x) {
while (i < t.size()) {
t[i] += x;
i |= i + 1;
}
}
int get(int i) {
int ans = 0;
while (i >= 0) {
ans += t[i];
i &= i + 1;
--i;
}
return ans;
}
private:
vector<int> t;
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, k;
cin >> n >> k;
vector<pair<int, pair<int, int>>> qrs;
int timer = -1;
for (int i = 0; i < n + k - 1; ++i) {
char ch;
cin >> ch;
if (ch == 'S') {
int u, v;
cin >> u >> v;
--u, --v;
edg[u].push_back({v, ++timer});
edg[v].push_back({u, timer});
} else if (ch == 'Q') {
int u, v;
cin >> u >> v;
--u, --v;
qrs.push_back({timer, {v, u}});
} else {
int v;
cin >> v;
--v;
qrs.push_back({timer, {v, -1}});
}
}
rt[0] = {0, -177013};
dfs(0);
for (int i = 0; i < n; ++i)
centrt[i] = -1;
centr_decompose(0);
vector<int> anss(k);
for (int i = 0; i < k; ++i) {
auto [t, qri] = qrs[i];
auto [v, u] = qri;
if (u == -1) {
anss[i] = ans_qr2(v, i, t);
} else {
way w = get_way(v, u);
if (w.incr && w.mxt <= t) {
anss[i] = -1;
} else {
anss[i] = -2;
}
}
}
fenwick tr;
tr.resize(n);
for (int v = 0; v < n; ++v) {
sort(subqr[v].rbegin(), subqr[v].rend());
sort(ways[v].begin(), ways[v].end());
int j = ways[v].size();
for (auto [hey, qi] : subqr[v]) {
auto [l, r] = hey;
while (j > 0 && ways[v][j - 1].first >= l) {
--j;
tr.add(ways[v][j].second, 1);
}
anss[qi] += tr.get(r);
//for (auto [l0, r0] : ways[v]) {
//if (l <= l0 && r0 <= r) {
//++anss[qi];
//}
//}
}
while (j < ways[v].size()) {
tr.add(ways[v][j].second, -1);
++j;
}
}
for (int i = 0; i < k; ++i) {
if (anss[i] == -1)
cout << "yes\n";
else if (anss[i] == -2)
cout << "no\n";
else
cout << anss[i] << '\n';
}
}
컴파일 시 표준 에러 (stderr) 메시지
servers.cpp: In member function 'void fenwick::add(int, int)':
servers.cpp:201:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
201 | while (i < t.size()) {
| ~~^~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:288:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
288 | while (j < ways[v].size()) {
| ~~^~~~~~~~~~~~~~~~
# | 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... |