oj.uz

Submission #536068

# Submission time Handle Problem Language Result Execution time Memory
536068 2022-03-12T09:14:52 Z 79brue Inside information (BOI21_servers) C++14
50 / 100
 645 ms 253352 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];
int increasingCnt[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] += increasingCnt[qa[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));
        increasingCnt[root]++;
    }

    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 119 ms 171212 KB Output is correct
2 Correct 139 ms 173444 KB Output is correct
3 Correct 138 ms 173312 KB Output is correct
4 Correct 150 ms 173348 KB Output is correct
5 Correct 133 ms 173224 KB Output is correct
6 Correct 133 ms 173040 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 119 ms 171212 KB Output is correct
2 Correct 139 ms 173444 KB Output is correct
3 Correct 138 ms 173312 KB Output is correct
4 Correct 150 ms 173348 KB Output is correct
5 Correct 133 ms 173224 KB Output is correct
6 Correct 133 ms 173040 KB Output is correct
7 Incorrect 122 ms 172048 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 127 ms 171372 KB Output is correct
2 Correct 312 ms 229504 KB Output is correct
3 Correct 303 ms 229408 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 127 ms 171372 KB Output is correct
2 Correct 312 ms 229504 KB Output is correct
3 Correct 303 ms 229408 KB Output is correct
4 Incorrect 124 ms 171668 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 171344 KB Output is correct
2 Correct 483 ms 239044 KB Output is correct
3 Correct 458 ms 238944 KB Output is correct
4 Correct 454 ms 253264 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 171344 KB Output is correct
2 Correct 483 ms 239044 KB Output is correct
3 Correct 458 ms 238944 KB Output is correct
4 Correct 454 ms 253264 KB Output is correct
5 Incorrect 139 ms 171820 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 143 ms 171468 KB Output is correct
2 Correct 461 ms 241616 KB Output is correct
3 Correct 434 ms 230872 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 171468 KB Output is correct
2 Correct 461 ms 241616 KB Output is correct
3 Correct 434 ms 230872 KB Output is correct
4 Incorrect 131 ms 171920 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 137 ms 171352 KB Output is correct
2 Correct 454 ms 239340 KB Output is correct
3 Correct 510 ms 239008 KB Output is correct
4 Correct 470 ms 253324 KB Output is correct
5 Correct 132 ms 171136 KB Output is correct
6 Correct 481 ms 241504 KB Output is correct
7 Correct 402 ms 230768 KB Output is correct
8 Correct 465 ms 230004 KB Output is correct
9 Correct 505 ms 230476 KB Output is correct
10 Correct 598 ms 239912 KB Output is correct
11 Correct 645 ms 239596 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 137 ms 171352 KB Output is correct
2 Correct 454 ms 239340 KB Output is correct
3 Correct 510 ms 239008 KB Output is correct
4 Correct 470 ms 253324 KB Output is correct
5 Correct 132 ms 171136 KB Output is correct
6 Correct 481 ms 241504 KB Output is correct
7 Correct 402 ms 230768 KB Output is correct
8 Correct 465 ms 230004 KB Output is correct
9 Correct 505 ms 230476 KB Output is correct
10 Correct 598 ms 239912 KB Output is correct
11 Correct 645 ms 239596 KB Output is correct
12 Incorrect 170 ms 171812 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 135 ms 171472 KB Output is correct
2 Correct 139 ms 173564 KB Output is correct
3 Correct 137 ms 173324 KB Output is correct
4 Correct 144 ms 173392 KB Output is correct
5 Correct 133 ms 173136 KB Output is correct
6 Correct 129 ms 173012 KB Output is correct
7 Correct 121 ms 171232 KB Output is correct
8 Correct 347 ms 229492 KB Output is correct
9 Correct 280 ms 229432 KB Output is correct
10 Correct 125 ms 171212 KB Output is correct
11 Correct 516 ms 238940 KB Output is correct
12 Correct 478 ms 239004 KB Output is correct
13 Correct 443 ms 253352 KB Output is correct
14 Correct 128 ms 171224 KB Output is correct
15 Correct 473 ms 241448 KB Output is correct
16 Correct 432 ms 230972 KB Output is correct
17 Correct 507 ms 229848 KB Output is correct
18 Correct 515 ms 230416 KB Output is correct
19 Correct 580 ms 239860 KB Output is correct
20 Correct 581 ms 239412 KB Output is correct
21 Correct 353 ms 229696 KB Output is correct
22 Correct 359 ms 229648 KB Output is correct
23 Correct 427 ms 229492 KB Output is correct
24 Correct 423 ms 229568 KB Output is correct
25 Correct 536 ms 236992 KB Output is correct
26 Correct 522 ms 229520 KB Output is correct
27 Correct 448 ms 229400 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 135 ms 171472 KB Output is correct
2 Correct 139 ms 173564 KB Output is correct
3 Correct 137 ms 173324 KB Output is correct
4 Correct 144 ms 173392 KB Output is correct
5 Correct 133 ms 173136 KB Output is correct
6 Correct 129 ms 173012 KB Output is correct
7 Correct 121 ms 171232 KB Output is correct
8 Correct 347 ms 229492 KB Output is correct
9 Correct 280 ms 229432 KB Output is correct
10 Correct 125 ms 171212 KB Output is correct
11 Correct 516 ms 238940 KB Output is correct
12 Correct 478 ms 239004 KB Output is correct
13 Correct 443 ms 253352 KB Output is correct
14 Correct 128 ms 171224 KB Output is correct
15 Correct 473 ms 241448 KB Output is correct
16 Correct 432 ms 230972 KB Output is correct
17 Correct 507 ms 229848 KB Output is correct
18 Correct 515 ms 230416 KB Output is correct
19 Correct 580 ms 239860 KB Output is correct
20 Correct 581 ms 239412 KB Output is correct
21 Correct 353 ms 229696 KB Output is correct
22 Correct 359 ms 229648 KB Output is correct
23 Correct 427 ms 229492 KB Output is correct
24 Correct 423 ms 229568 KB Output is correct
25 Correct 536 ms 236992 KB Output is correct
26 Correct 522 ms 229520 KB Output is correct
27 Correct 448 ms 229400 KB Output is correct
28 Incorrect 147 ms 172056 KB Extra information in the output file
29 Halted 0 ms 0 KB -