Submission #536069

#	Time	Username	Problem	Language	Result	Execution time	Memory
536069		79brue	Inside information (BOI21_servers)	C++14	52.50 / 100	680 ms	265312 KiB

servers

#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 (stderr)

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
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5