oj.uz

Submission #536026

# Submission time Handle Problem Language Result Execution time Memory
536026 2022-03-12T07:09:25 Z 79brue Inside information (BOI21_servers) C++14
50 / 100
 378 ms 69896 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, q;
char qt[300002];
int qa[300002], qb[300002];
vector<pair<int, int> > link[300002];

void makeCentroidTree();
bool query(int, int, int);
int query(int);

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));
    }

    makeCentroidTree();
    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", query(qa[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];

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){
    increasing[x][dp] = inc, decreasing[x][dp] = dec;
    rootLinkWeight[x][dp] = rootWeight1, parWeight[x][dp] = 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);
    }
}

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);
    }

    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;
}

int query(int x){
    return 0;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf(" %c %d", &qt[i], &qa[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:21:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         if(qt[i]!='C') scanf("%d", &qb[i]);
      |                        ~~~~~^~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15820 KB Output is correct
2 Correct 50 ms 17240 KB Output is correct
3 Correct 50 ms 18648 KB Output is correct
4 Correct 52 ms 18692 KB Output is correct
5 Correct 52 ms 18868 KB Output is correct
6 Correct 61 ms 18616 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15820 KB Output is correct
2 Correct 50 ms 17240 KB Output is correct
3 Correct 50 ms 18648 KB Output is correct
4 Correct 52 ms 18692 KB Output is correct
5 Correct 52 ms 18868 KB Output is correct
6 Correct 61 ms 18616 KB Output is correct
7 Incorrect 58 ms 16736 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 44 ms 15800 KB Output is correct
2 Correct 146 ms 56932 KB Output is correct
3 Correct 177 ms 59944 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15800 KB Output is correct
2 Correct 146 ms 56932 KB Output is correct
3 Correct 177 ms 59944 KB Output is correct
4 Incorrect 45 ms 16676 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 45 ms 15860 KB Output is correct
2 Correct 339 ms 66560 KB Output is correct
3 Correct 322 ms 69896 KB Output is correct
4 Correct 203 ms 69776 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15860 KB Output is correct
2 Correct 339 ms 66560 KB Output is correct
3 Correct 322 ms 69896 KB Output is correct
4 Correct 203 ms 69776 KB Output is correct
5 Incorrect 49 ms 16636 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 49 ms 15844 KB Output is correct
2 Correct 178 ms 57928 KB Output is correct
3 Correct 257 ms 61208 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15844 KB Output is correct
2 Correct 178 ms 57928 KB Output is correct
3 Correct 257 ms 61208 KB Output is correct
4 Incorrect 48 ms 16648 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 47 ms 15988 KB Output is correct
2 Correct 297 ms 66592 KB Output is correct
3 Correct 333 ms 69880 KB Output is correct
4 Correct 192 ms 69752 KB Output is correct
5 Correct 64 ms 16672 KB Output is correct
6 Correct 179 ms 61088 KB Output is correct
7 Correct 250 ms 61344 KB Output is correct
8 Correct 325 ms 61268 KB Output is correct
9 Correct 372 ms 61192 KB Output is correct
10 Correct 333 ms 64724 KB Output is correct
11 Correct 378 ms 64548 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 15988 KB Output is correct
2 Correct 297 ms 66592 KB Output is correct
3 Correct 333 ms 69880 KB Output is correct
4 Correct 192 ms 69752 KB Output is correct
5 Correct 64 ms 16672 KB Output is correct
6 Correct 179 ms 61088 KB Output is correct
7 Correct 250 ms 61344 KB Output is correct
8 Correct 325 ms 61268 KB Output is correct
9 Correct 372 ms 61192 KB Output is correct
10 Correct 333 ms 64724 KB Output is correct
11 Correct 378 ms 64548 KB Output is correct
12 Incorrect 45 ms 16668 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 44 ms 15828 KB Output is correct
2 Correct 53 ms 17248 KB Output is correct
3 Correct 56 ms 18672 KB Output is correct
4 Correct 53 ms 18640 KB Output is correct
5 Correct 51 ms 18932 KB Output is correct
6 Correct 49 ms 18640 KB Output is correct
7 Correct 44 ms 16792 KB Output is correct
8 Correct 166 ms 59904 KB Output is correct
9 Correct 149 ms 59868 KB Output is correct
10 Correct 45 ms 16688 KB Output is correct
11 Correct 329 ms 69852 KB Output is correct
12 Correct 340 ms 69884 KB Output is correct
13 Correct 190 ms 69724 KB Output is correct
14 Correct 48 ms 16668 KB Output is correct
15 Correct 185 ms 61128 KB Output is correct
16 Correct 255 ms 61240 KB Output is correct
17 Correct 331 ms 61168 KB Output is correct
18 Correct 355 ms 61156 KB Output is correct
19 Correct 364 ms 64780 KB Output is correct
20 Correct 346 ms 64536 KB Output is correct
21 Correct 169 ms 60220 KB Output is correct
22 Correct 181 ms 60236 KB Output is correct
23 Correct 236 ms 60320 KB Output is correct
24 Correct 280 ms 60484 KB Output is correct
25 Correct 376 ms 66848 KB Output is correct
26 Correct 305 ms 60904 KB Output is correct
27 Correct 288 ms 61072 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15828 KB Output is correct
2 Correct 53 ms 17248 KB Output is correct
3 Correct 56 ms 18672 KB Output is correct
4 Correct 53 ms 18640 KB Output is correct
5 Correct 51 ms 18932 KB Output is correct
6 Correct 49 ms 18640 KB Output is correct
7 Correct 44 ms 16792 KB Output is correct
8 Correct 166 ms 59904 KB Output is correct
9 Correct 149 ms 59868 KB Output is correct
10 Correct 45 ms 16688 KB Output is correct
11 Correct 329 ms 69852 KB Output is correct
12 Correct 340 ms 69884 KB Output is correct
13 Correct 190 ms 69724 KB Output is correct
14 Correct 48 ms 16668 KB Output is correct
15 Correct 185 ms 61128 KB Output is correct
16 Correct 255 ms 61240 KB Output is correct
17 Correct 331 ms 61168 KB Output is correct
18 Correct 355 ms 61156 KB Output is correct
19 Correct 364 ms 64780 KB Output is correct
20 Correct 346 ms 64536 KB Output is correct
21 Correct 169 ms 60220 KB Output is correct
22 Correct 181 ms 60236 KB Output is correct
23 Correct 236 ms 60320 KB Output is correct
24 Correct 280 ms 60484 KB Output is correct
25 Correct 376 ms 66848 KB Output is correct
26 Correct 305 ms 60904 KB Output is correct
27 Correct 288 ms 61072 KB Output is correct
28 Incorrect 47 ms 16700 KB Extra information in the output file
29 Halted 0 ms 0 KB -