oj.uz

Submission #536025

# Submission time Handle Problem Language Result Execution time Memory
536025 2022-03-12T07:08:16 Z 79brue Inside information (BOI21_servers) C++14
0 / 100
 330 ms 69868 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){
    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
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16740 KB Output is correct
2 Incorrect 51 ms 18624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16740 KB Output is correct
2 Incorrect 51 ms 18624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16792 KB Output is correct
2 Incorrect 154 ms 59892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16792 KB Output is correct
2 Incorrect 154 ms 59892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16712 KB Output is correct
2 Incorrect 320 ms 69868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16712 KB Output is correct
2 Incorrect 320 ms 69868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16716 KB Output is correct
2 Incorrect 201 ms 61096 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16716 KB Output is correct
2 Incorrect 201 ms 61096 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16712 KB Output is correct
2 Incorrect 330 ms 69844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16712 KB Output is correct
2 Incorrect 330 ms 69844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 16760 KB Output is correct
2 Incorrect 60 ms 18544 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 16760 KB Output is correct
2 Incorrect 60 ms 18544 KB Output isn't correct
3 Halted 0 ms 0 KB -