oj.uz

답안 #529479

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
529479 2022-02-23T04:27:20 Z qwerasdfzxcl Inside information (BOI21_servers) C++14
0 / 100
 42 ms 9664 KB 
#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];
        return gou[cdep[u]][s] && god[cdep[u]][e] && idx[cdep[u]][s1] < idx[cdep[u]][e1];
    }

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

Compilation message

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:122:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         scanf(" %c %d", &op, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
servers.cpp:127:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         if (op!='C') scanf("%d", &y);
      |                      ~~~~~^~~~~~~~~~

Subtask #1
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 9540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 9540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 9576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 9576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 36 ms 9572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 36 ms 9572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 9632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 9632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 41 ms 9664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 41 ms 9664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 9560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 9560 KB Output isn't correct
2 Halted 0 ms 0 KB -