제출 #529486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529486		qwerasdfzxcl	Inside information (BOI21_servers)	C++14	52.50 / 100	530 ms	43028 KiB

servers

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
constexpr int MAXN = 120120, LOGN = 20;
vector<pair<int, int>> adj[MAXN];

struct Seg{
    vector<int> tree;
    int sz;
    void init(int n){
        sz = n+1;
        tree.resize(sz*2);
    }
    void update(int p, int x){
        for (tree[p+=sz]+=x;p>1;p>>=1) tree[p>>1] = tree[p] + tree[p^1];
    }
    int query(int l){
        int r = sz, ret = 0;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret += tree[l++];
            if (r&1) ret += tree[--r];
        }
        return ret;
    }
};

struct Cent{
    int sz[MAXN], cpa[MAXN], cdep[MAXN];
    bool visited[MAXN];

    int subt[LOGN][MAXN], idx[LOGN][MAXN], pt[MAXN];
    bool gou[LOGN][MAXN], god[LOGN][MAXN];
    Seg tree[MAXN];

    int getsz(int s, int pa = -1){
        sz[s] = 1;
        for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa) sz[s] += getsz(v, s);
        return sz[s];
    }
    int getcent(int s, int cap, int pa = -1){
        for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa && sz[v]*2 > cap) return getcent(v, cap, s);
        return s;
    }

    void dfs1(int s, int root, int pa, int dep){
        subt[dep][s] = root;
        for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa) dfs1(v, root, s, dep);
    }

    void dnc(int s, int dep = 1, int pa = -1){
        getsz(s);
        int c = getcent(s, sz[s]);

        for (auto &[v, w]:adj[c]) if (!visited[v]) dfs1(v, v, c, dep); ///init subt
        cdep[c] = dep, cpa[c] = pa;
        tree[c].init(adj[c].size());
        visited[c] = 1;
        gou[dep][c] = god[dep][c] = 1;

        for (auto &[v, w]:adj[c]) if (!visited[v]){
            dnc(v, dep+1, c);
        }
    }

    void dfs2(int s, int dep, int pa, int cst){
        gou[dep][s] = 1;
        for (auto &[v, w]:adj[s]) if (cdep[v]>dep && v!=pa && w!=-1 && w<cst) dfs2(v, dep, s, w);
    }

    void update(int v, int w, int cst){
        if (cdep[v]>cdep[w]) swap(v, w);

        idx[cdep[v]][w] = ++pt[v];
        tree[v].update(idx[cdep[v]][w], 1);
        dfs2(w, cdep[v], v, cst);

        god[cdep[v]][w] = 1;
        for (int s=cpa[v];s!=-1;s=cpa[s]){
            if (god[cdep[s]][v]) god[cdep[s]][w] = 1;
            else if (god[cdep[s]][w]) god[cdep[s]][v] = 1;

            int pos = idx[cdep[s]][subt[cdep[s]][v]];
            tree[s].update(pos, 1);
        }
    }

    bool query(int s, int e){
        if (s==e) return 1;
        int u = s, v = e;
        if (cdep[u]>cdep[v]) swap(u, v);
        while(cdep[u]!=cdep[v]) v = cpa[v];
        while(u!=v) u = cpa[u], v = cpa[v];

        assert(u!=-1);
        int s1 = subt[cdep[u]][s], e1 = subt[cdep[u]][e];
        bool flag = idx[cdep[u]][s1] < idx[cdep[u]][e1];
        if (s1==0 || e1==0) flag = 1;
        return gou[cdep[u]][s] && god[cdep[u]][e] && flag;
    }

    int count(int s){
        int ret = tree[s].query(0)+1;
        //if (s==2) printf("%d %d: %d\n",s, cdep[s], ret);
        for (int c=cpa[s];c!=-1;c=cpa[c]) if (gou[cdep[c]][s]){
            int tmp = subt[cdep[c]][s];
            int pos = idx[cdep[c]][tmp];
            ret += tree[c].query(pos+1)+1;
            //if (s==2) printf("%d %d: %d\n", c, cdep[c], ret);
        }
        return ret;
    }
}cent;

struct Query{
    char op;
    int x, y;
    Query(){}
    Query(char _op, int _x, int _y): op(_op), x(_x), y(_y) {}
}Q[MAXN*2];

int main(){
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i=1,cnt=1;i<=n+q-1;i++){
        char op;
        int x, y = -1;
        scanf(" %c %d", &op, &x);
        if (op!='C') scanf("%d", &y);

        if (op=='S'){
            adj[x].emplace_back(y, cnt);
            adj[y].emplace_back(x, cnt);
            cnt++;
        }
        Q[i] = Query(op, x, y);
    }

    cent.dnc(1);

    for (int i=1,cnt=1;i<=n+q-1;i++){
        if (Q[i].op=='S'){
            cent.update(Q[i].x, Q[i].y, cnt);
            cnt++;
        }
        else if (Q[i].op=='Q'){
            if (cent.query(Q[i].y, Q[i].x)) printf("yes\n");
            else printf("no\n");
        }
        else{
            printf("%d\n", cent.count(Q[i].x));
        }
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

servers.cpp: In member function 'int Cent::getsz(int, int)':
servers.cpp:38:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa) sz[s] += getsz(v, s);
      |                    ^
servers.cpp: In member function 'int Cent::getcent(int, int, int)':
servers.cpp:42:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa && sz[v]*2 > cap) return getcent(v, cap, s);
      |                    ^
servers.cpp: In member function 'void Cent::dfs1(int, int, int, int)':
servers.cpp:48:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa) dfs1(v, root, s, dep);
      |                    ^
servers.cpp: In member function 'void Cent::dnc(int, int, int)':
servers.cpp:55:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |         for (auto &[v, w]:adj[c]) if (!visited[v]) dfs1(v, v, c, dep); ///init subt
      |                    ^
servers.cpp:61:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |         for (auto &[v, w]:adj[c]) if (!visited[v]){
      |                    ^
servers.cpp: In member function 'void Cent::dfs2(int, int, int, int)':
servers.cpp:68:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |         for (auto &[v, w]:adj[s]) if (cdep[v]>dep && v!=pa && w!=-1 && w<cst) dfs2(v, dep, s, w);
      |                    ^
servers.cpp: In function 'int main()':
servers.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         scanf(" %c %d", &op, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
servers.cpp:129:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         if (op!='C') scanf("%d", &y);
      |                      ~~~~~^~~~~~~~~~

• 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