oj.uz

Submission #536069

# Submission time Handle Problem Language Result Execution time Memory
536069 2022-03-12T09:19:20 Z 79brue Inside information (BOI21_servers) C++14
52.5 / 100
 680 ms 265312 KB 
#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

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]);
      |                        ~~~~~^~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 129 ms 178380 KB Output is correct
2 Correct 141 ms 180504 KB Output is correct
3 Correct 137 ms 180484 KB Output is correct
4 Correct 146 ms 180484 KB Output is correct
5 Correct 146 ms 180248 KB Output is correct
6 Correct 133 ms 180156 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 129 ms 178380 KB Output is correct
2 Correct 141 ms 180504 KB Output is correct
3 Correct 137 ms 180484 KB Output is correct
4 Correct 146 ms 180484 KB Output is correct
5 Correct 146 ms 180248 KB Output is correct
6 Correct 133 ms 180156 KB Output is correct
7 Correct 127 ms 179136 KB Output is correct
8 Incorrect 169 ms 184836 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 125 ms 178336 KB Output is correct
2 Correct 323 ms 236848 KB Output is correct
3 Correct 297 ms 236880 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 125 ms 178336 KB Output is correct
2 Correct 323 ms 236848 KB Output is correct
3 Correct 297 ms 236880 KB Output is correct
4 Correct 128 ms 178736 KB Output is correct
5 Correct 319 ms 241344 KB Output is correct
6 Correct 266 ms 239376 KB Output is correct
7 Correct 274 ms 242304 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 178216 KB Output is correct
2 Correct 480 ms 247560 KB Output is correct
3 Correct 507 ms 247588 KB Output is correct
4 Correct 453 ms 265216 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 178216 KB Output is correct
2 Correct 480 ms 247560 KB Output is correct
3 Correct 507 ms 247588 KB Output is correct
4 Correct 453 ms 265216 KB Output is correct
5 Incorrect 126 ms 178852 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 178252 KB Output is correct
2 Correct 481 ms 252916 KB Output is correct
3 Correct 433 ms 239860 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 178252 KB Output is correct
2 Correct 481 ms 252916 KB Output is correct
3 Correct 433 ms 239860 KB Output is correct
4 Incorrect 126 ms 178972 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 133 ms 178296 KB Output is correct
2 Correct 487 ms 247692 KB Output is correct
3 Correct 488 ms 247556 KB Output is correct
4 Correct 460 ms 265280 KB Output is correct
5 Correct 127 ms 178228 KB Output is correct
6 Correct 503 ms 252916 KB Output is correct
7 Correct 424 ms 239932 KB Output is correct
8 Correct 501 ms 237948 KB Output is correct
9 Correct 511 ms 238612 KB Output is correct
10 Correct 623 ms 250284 KB Output is correct
11 Correct 633 ms 249880 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 133 ms 178296 KB Output is correct
2 Correct 487 ms 247692 KB Output is correct
3 Correct 488 ms 247556 KB Output is correct
4 Correct 460 ms 265280 KB Output is correct
5 Correct 127 ms 178228 KB Output is correct
6 Correct 503 ms 252916 KB Output is correct
7 Correct 424 ms 239932 KB Output is correct
8 Correct 501 ms 237948 KB Output is correct
9 Correct 511 ms 238612 KB Output is correct
10 Correct 623 ms 250284 KB Output is correct
11 Correct 633 ms 249880 KB Output is correct
12 Incorrect 133 ms 178932 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 133 ms 178236 KB Output is correct
2 Correct 161 ms 180352 KB Output is correct
3 Correct 135 ms 180364 KB Output is correct
4 Correct 153 ms 180568 KB Output is correct
5 Correct 156 ms 180156 KB Output is correct
6 Correct 147 ms 180068 KB Output is correct
7 Correct 138 ms 178272 KB Output is correct
8 Correct 315 ms 236800 KB Output is correct
9 Correct 322 ms 236844 KB Output is correct
10 Correct 127 ms 178252 KB Output is correct
11 Correct 542 ms 247604 KB Output is correct
12 Correct 530 ms 247616 KB Output is correct
13 Correct 515 ms 265312 KB Output is correct
14 Correct 133 ms 178236 KB Output is correct
15 Correct 466 ms 253028 KB Output is correct
16 Correct 448 ms 239796 KB Output is correct
17 Correct 589 ms 238020 KB Output is correct
18 Correct 655 ms 238428 KB Output is correct
19 Correct 680 ms 250296 KB Output is correct
20 Correct 677 ms 249860 KB Output is correct
21 Correct 345 ms 237456 KB Output is correct
22 Correct 320 ms 237452 KB Output is correct
23 Correct 400 ms 237608 KB Output is correct
24 Correct 412 ms 237724 KB Output is correct
25 Correct 577 ms 245768 KB Output is correct
26 Correct 507 ms 237872 KB Output is correct
27 Correct 490 ms 237780 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 133 ms 178236 KB Output is correct
2 Correct 161 ms 180352 KB Output is correct
3 Correct 135 ms 180364 KB Output is correct
4 Correct 153 ms 180568 KB Output is correct
5 Correct 156 ms 180156 KB Output is correct
6 Correct 147 ms 180068 KB Output is correct
7 Correct 138 ms 178272 KB Output is correct
8 Correct 315 ms 236800 KB Output is correct
9 Correct 322 ms 236844 KB Output is correct
10 Correct 127 ms 178252 KB Output is correct
11 Correct 542 ms 247604 KB Output is correct
12 Correct 530 ms 247616 KB Output is correct
13 Correct 515 ms 265312 KB Output is correct
14 Correct 133 ms 178236 KB Output is correct
15 Correct 466 ms 253028 KB Output is correct
16 Correct 448 ms 239796 KB Output is correct
17 Correct 589 ms 238020 KB Output is correct
18 Correct 655 ms 238428 KB Output is correct
19 Correct 680 ms 250296 KB Output is correct
20 Correct 677 ms 249860 KB Output is correct
21 Correct 345 ms 237456 KB Output is correct
22 Correct 320 ms 237452 KB Output is correct
23 Correct 400 ms 237608 KB Output is correct
24 Correct 412 ms 237724 KB Output is correct
25 Correct 577 ms 245768 KB Output is correct
26 Correct 507 ms 237872 KB Output is correct
27 Correct 490 ms 237780 KB Output is correct
28 Correct 137 ms 179080 KB Output is correct
29 Incorrect 145 ms 184812 KB Extra information in the output file
30 Halted 0 ms 0 KB -