This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Fenwick {
int n = 300000;
int tree[300002];
void add(int x, int v){
while(x<=n){
tree[x] += v;
x += x&-x;
}
}
int sum(int x){
int ret = 0;
while(x){
ret += tree[x];
x -= x&-x;
}
return ret;
}
int sum(int l, int r){
return sum(r) - sum(l-1);
}
} tree;
int n, q;
char qt[300002];
int qa[300002], qb[300002];
int qans[300002];
vector<pair<int, int> > link[300002];
vector<int> increasingVec[300002];
void makeCentroidTree();
bool query(int, int, int);
void query(int, int);
void processQueries();
int main(){
scanf("%d %d", &n, &q);
q += n-1;
for(int i=1; i<=q; i++){
scanf(" %c %d", &qt[i], &qa[i]);
if(qt[i]!='C') scanf("%d", &qb[i]);
if(qt[i]=='S') link[qa[i]].push_back(make_pair(qb[i], i)), link[qb[i]].push_back(make_pair(qa[i], i));
}
for(int i=1; i<=n; i++){
sort(link[i].begin(), link[i].end(), [&](auto x, auto y){
return x.second < y.second;
});
}
makeCentroidTree();
for(int i=1; i<=q; i++){
if(qt[i] == 'C'){
query(qa[i], i);
qans[i] += upper_bound(increasingVec[qa[i]].begin(), increasingVec[qa[i]].end(), i) - increasingVec[qa[i]].begin();
qans[i] += 1;
}
}
processQueries();
for(int i=1; i<=q; i++){
if(qt[i]=='S') continue;
if(qt[i]=='Q'){
printf("%s\n", query(qa[i], qb[i], i) ? "yes" : "no");
}
else{
printf("%d\n", qans[i]);
}
}
}
int centroidRoot;
vector<int> centroidChild[300002];
int centroidDepth[300002], centroidPar[300002], centroidAncestor[300002][20];
bool centroidUsed[300002];
int subTreeSize[300002];
bool increasing[300002][20], decreasing[300002][20];
int rootLinkWeight[300002][20], parWeight[300002][20];
int rootLink[300002][20];
vector<pair<int, int> > vec[300002];
vector<pair<int, int> > vecSpecific[300002][20];
struct Query {
int t; /// 0: 점 추가, 1: 쿼리
int x, y, w, i;
Query(){}
Query(int t, int x, int y, int w, int i): t(t), x(x), y(y), w(w), i(i){}
bool operator<(const Query &r)const{
if(y==r.y) return t<r.t;
return y<r.y;
}
};
vector<Query> queries[300002];
void subTreeDfs(int x, int p=-1){
subTreeSize[x] = 1;
for(auto y: link[x]){
if(y.first==p || centroidUsed[y.first]) continue;
subTreeDfs(y.first, x);
subTreeSize[x] += subTreeSize[y.first];
}
}
void getCentroid(int x, int p, int &c, int lim){
if(subTreeSize[x] < lim) return;
c = x;
for(auto y: link[x]){
if(y.first==p || centroidUsed[y.first]) continue;
getCentroid(y.first, x, c, lim);
}
}
void makeDatabase(int x, int p, int dp, int parWeight1, int rootWeight1, bool inc, bool dec, int root, int underRoot){
increasing[x][dp] = inc, decreasing[x][dp] = dec;
rootLinkWeight[x][dp] = rootWeight1, parWeight[x][dp] = parWeight1;
rootLink[x][dp] = underRoot;
if(inc){
vec[root].push_back(make_pair(rootWeight1, parWeight1));
vecSpecific[underRoot][dp].push_back(make_pair(rootWeight1, parWeight1));
increasingVec[root].push_back(parWeight1);
}
for(auto y: link[x]){
if(y.first==p || centroidUsed[y.first]) continue;
makeDatabase(y.first, x, dp, y.second, rootWeight1, inc && parWeight1 < y.second, dec && parWeight1 > y.second,
root, underRoot);
}
}
int findCentroid(int x, int dp=0){
subTreeDfs(x);
int s = subTreeSize[x];
int c = x, lim = (s+1)/2;
getCentroid(x, -1, c, lim);
centroidUsed[c] = 1;
centroidDepth[c] = dp;
for(auto y: link[c]){
if(centroidUsed[y.first]) continue;
makeDatabase(y.first, c, dp, y.second, y.second, 1, 1, c, y.first);
}
for(auto y: link[c]){
if(centroidUsed[y.first]) continue;
int tmp = findCentroid(y.first, dp+1);
centroidPar[tmp] = c;
centroidChild[c].push_back(tmp);
}
return c;
}
void makeCentroidTree(){
centroidRoot = findCentroid(1);
for(int i=1; i<=n; i++) centroidAncestor[i][centroidDepth[i]] = i;
for(int i=1; i<=n; i++){
int dp = centroidDepth[i];
for(int j=dp-1; j>=0; j--) centroidAncestor[i][j] = centroidPar[centroidAncestor[i][j+1]];
}
}
bool query(int A, int B, int i){
if(A==B) return true;
swap(A, B);
int d=min(centroidDepth[A], centroidDepth[B]);
while(centroidAncestor[A][d] != centroidAncestor[B][d]) d--;
int root = centroidAncestor[A][d];
if(root == A) return increasing[B][d] && parWeight[B][d] <= i;
if(root == B) return decreasing[A][d] && rootLinkWeight[A][d] <= i;
return decreasing[A][d] && increasing[B][d] && rootLinkWeight[A][d] < rootLinkWeight[B][d] && parWeight[B][d] <= i;
}
void query(int x, int i){
for(int d=centroidDepth[x]-1; d>=0; d--){
if(!decreasing[x][d]) continue;
if(i >= rootLinkWeight[x][d]) qans[i]++;
queries[centroidAncestor[x][d]].push_back(Query(1, rootLinkWeight[x][d]+1, i, 1, i));
}
}
void processQueries(){
for(int i=1; i<=n; i++){
sort(vec[i].begin(), vec[i].end());
for(int d=0; d<20; d++){
sort(vecSpecific[i][d].begin(), vecSpecific[i][d].end());
}
}
for(int i=1; i<=n; i++){
vector<Query> qvec = queries[i];
for(pair<int, int> p: vec[i]) qvec.push_back(Query(0, p.first, p.second, 1, 0));
sort(qvec.begin(), qvec.end());
for(Query query: qvec){
if(query.t == 0) tree.add(query.x, query.w);
else qans[query.i] += tree.sum(query.x, tree.n);
}
for(Query query: qvec){
if(query.t == 0) tree.add(query.x, -query.w);
}
}
}
Compilation message (stderr)
servers.cpp: In function 'int main()':
servers.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf(" %c %d", &qt[i], &qa[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:49:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | if(qt[i]!='C') scanf("%d", &qb[i]);
| ~~~~~^~~~~~~~~~~~~~
# | 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... |