oj.uz

Submission #536059

# Submission time Handle Problem Language Result Execution time Memory
536059 2022-03-12T08:44:08 Z 79brue Inside information (BOI21_servers) C++14
50 / 100
 690 ms 253304 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;
        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 117 ms 171264 KB Output is correct
2 Correct 127 ms 173444 KB Output is correct
3 Correct 133 ms 173392 KB Output is correct
4 Correct 137 ms 173440 KB Output is correct
5 Correct 121 ms 173164 KB Output is correct
6 Correct 121 ms 173096 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 117 ms 171264 KB Output is correct
2 Correct 127 ms 173444 KB Output is correct
3 Correct 133 ms 173392 KB Output is correct
4 Correct 137 ms 173440 KB Output is correct
5 Correct 121 ms 173164 KB Output is correct
6 Correct 121 ms 173096 KB Output is correct
7 Incorrect 118 ms 172092 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 130 ms 171344 KB Output is correct
2 Correct 277 ms 229444 KB Output is correct
3 Correct 360 ms 229272 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 130 ms 171344 KB Output is correct
2 Correct 277 ms 229444 KB Output is correct
3 Correct 360 ms 229272 KB Output is correct
4 Incorrect 115 ms 171736 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 120 ms 171304 KB Output is correct
2 Correct 464 ms 239020 KB Output is correct
3 Correct 460 ms 238944 KB Output is correct
4 Correct 432 ms 253244 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 171304 KB Output is correct
2 Correct 464 ms 239020 KB Output is correct
3 Correct 460 ms 238944 KB Output is correct
4 Correct 432 ms 253244 KB Output is correct
5 Incorrect 131 ms 171752 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 122 ms 171264 KB Output is correct
2 Correct 493 ms 241552 KB Output is correct
3 Correct 395 ms 230816 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 171264 KB Output is correct
2 Correct 493 ms 241552 KB Output is correct
3 Correct 395 ms 230816 KB Output is correct
4 Incorrect 139 ms 171884 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 122 ms 171212 KB Output is correct
2 Correct 468 ms 239016 KB Output is correct
3 Correct 449 ms 238836 KB Output is correct
4 Correct 449 ms 253304 KB Output is correct
5 Correct 128 ms 171212 KB Output is correct
6 Correct 522 ms 241400 KB Output is correct
7 Correct 461 ms 230772 KB Output is correct
8 Correct 539 ms 229960 KB Output is correct
9 Correct 510 ms 230524 KB Output is correct
10 Correct 654 ms 239864 KB Output is correct
11 Correct 690 ms 239452 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 122 ms 171212 KB Output is correct
2 Correct 468 ms 239016 KB Output is correct
3 Correct 449 ms 238836 KB Output is correct
4 Correct 449 ms 253304 KB Output is correct
5 Correct 128 ms 171212 KB Output is correct
6 Correct 522 ms 241400 KB Output is correct
7 Correct 461 ms 230772 KB Output is correct
8 Correct 539 ms 229960 KB Output is correct
9 Correct 510 ms 230524 KB Output is correct
10 Correct 654 ms 239864 KB Output is correct
11 Correct 690 ms 239452 KB Output is correct
12 Incorrect 130 ms 171736 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 128 ms 171244 KB Output is correct
2 Correct 136 ms 173360 KB Output is correct
3 Correct 130 ms 173384 KB Output is correct
4 Correct 145 ms 173428 KB Output is correct
5 Correct 157 ms 173052 KB Output is correct
6 Correct 142 ms 173076 KB Output is correct
7 Correct 114 ms 171228 KB Output is correct
8 Correct 324 ms 229340 KB Output is correct
9 Correct 288 ms 229432 KB Output is correct
10 Correct 128 ms 171228 KB Output is correct
11 Correct 442 ms 238880 KB Output is correct
12 Correct 457 ms 238924 KB Output is correct
13 Correct 413 ms 253256 KB Output is correct
14 Correct 121 ms 171136 KB Output is correct
15 Correct 436 ms 241468 KB Output is correct
16 Correct 418 ms 230824 KB Output is correct
17 Correct 502 ms 229852 KB Output is correct
18 Correct 474 ms 230520 KB Output is correct
19 Correct 569 ms 239908 KB Output is correct
20 Correct 606 ms 239464 KB Output is correct
21 Correct 291 ms 229668 KB Output is correct
22 Correct 306 ms 229676 KB Output is correct
23 Correct 369 ms 229404 KB Output is correct
24 Correct 368 ms 229492 KB Output is correct
25 Correct 504 ms 237024 KB Output is correct
26 Correct 476 ms 229472 KB Output is correct
27 Correct 442 ms 229408 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 128 ms 171244 KB Output is correct
2 Correct 136 ms 173360 KB Output is correct
3 Correct 130 ms 173384 KB Output is correct
4 Correct 145 ms 173428 KB Output is correct
5 Correct 157 ms 173052 KB Output is correct
6 Correct 142 ms 173076 KB Output is correct
7 Correct 114 ms 171228 KB Output is correct
8 Correct 324 ms 229340 KB Output is correct
9 Correct 288 ms 229432 KB Output is correct
10 Correct 128 ms 171228 KB Output is correct
11 Correct 442 ms 238880 KB Output is correct
12 Correct 457 ms 238924 KB Output is correct
13 Correct 413 ms 253256 KB Output is correct
14 Correct 121 ms 171136 KB Output is correct
15 Correct 436 ms 241468 KB Output is correct
16 Correct 418 ms 230824 KB Output is correct
17 Correct 502 ms 229852 KB Output is correct
18 Correct 474 ms 230520 KB Output is correct
19 Correct 569 ms 239908 KB Output is correct
20 Correct 606 ms 239464 KB Output is correct
21 Correct 291 ms 229668 KB Output is correct
22 Correct 306 ms 229676 KB Output is correct
23 Correct 369 ms 229404 KB Output is correct
24 Correct 368 ms 229492 KB Output is correct
25 Correct 504 ms 237024 KB Output is correct
26 Correct 476 ms 229472 KB Output is correct
27 Correct 442 ms 229408 KB Output is correct
28 Incorrect 139 ms 172084 KB Extra information in the output file
29 Halted 0 ms 0 KB -