oj.uz

Submission #529486

# Submission time Handle Problem Language Result Execution time Memory
529486 2022-02-23T04:35:29 Z qwerasdfzxcl Inside information (BOI21_servers) C++14
52.5 / 100
 530 ms 43028 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];
        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;
}

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: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

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8644 KB Output is correct
2 Correct 55 ms 10928 KB Output is correct
3 Correct 43 ms 10660 KB Output is correct
4 Correct 55 ms 11072 KB Output is correct
5 Correct 48 ms 11080 KB Output is correct
6 Correct 40 ms 10588 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8644 KB Output is correct
2 Correct 55 ms 10928 KB Output is correct
3 Correct 43 ms 10660 KB Output is correct
4 Correct 55 ms 11072 KB Output is correct
5 Correct 48 ms 11080 KB Output is correct
6 Correct 40 ms 10588 KB Output is correct
7 Incorrect 35 ms 9644 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 39 ms 8644 KB Output is correct
2 Correct 126 ms 25272 KB Output is correct
3 Correct 136 ms 25304 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 8644 KB Output is correct
2 Correct 126 ms 25272 KB Output is correct
3 Correct 136 ms 25304 KB Output is correct
4 Correct 34 ms 9536 KB Output is correct
5 Correct 136 ms 25104 KB Output is correct
6 Correct 128 ms 24392 KB Output is correct
7 Correct 111 ms 24500 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8744 KB Output is correct
2 Correct 530 ms 41996 KB Output is correct
3 Correct 524 ms 42068 KB Output is correct
4 Correct 202 ms 42476 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8744 KB Output is correct
2 Correct 530 ms 41996 KB Output is correct
3 Correct 524 ms 42068 KB Output is correct
4 Correct 202 ms 42476 KB Output is correct
5 Incorrect 34 ms 9540 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 41 ms 8900 KB Output is correct
2 Correct 182 ms 34196 KB Output is correct
3 Correct 404 ms 33728 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8900 KB Output is correct
2 Correct 182 ms 34196 KB Output is correct
3 Correct 404 ms 33728 KB Output is correct
4 Incorrect 34 ms 9540 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 34 ms 8784 KB Output is correct
2 Correct 523 ms 42056 KB Output is correct
3 Correct 517 ms 42080 KB Output is correct
4 Correct 231 ms 42540 KB Output is correct
5 Correct 34 ms 9616 KB Output is correct
6 Correct 192 ms 34320 KB Output is correct
7 Correct 367 ms 33724 KB Output is correct
8 Correct 365 ms 40460 KB Output is correct
9 Correct 444 ms 39860 KB Output is correct
10 Correct 480 ms 43028 KB Output is correct
11 Correct 465 ms 42944 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8784 KB Output is correct
2 Correct 523 ms 42056 KB Output is correct
3 Correct 517 ms 42080 KB Output is correct
4 Correct 231 ms 42540 KB Output is correct
5 Correct 34 ms 9616 KB Output is correct
6 Correct 192 ms 34320 KB Output is correct
7 Correct 367 ms 33724 KB Output is correct
8 Correct 365 ms 40460 KB Output is correct
9 Correct 444 ms 39860 KB Output is correct
10 Correct 480 ms 43028 KB Output is correct
11 Correct 465 ms 42944 KB Output is correct
12 Incorrect 33 ms 9540 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 35 ms 8644 KB Output is correct
2 Correct 46 ms 10984 KB Output is correct
3 Correct 41 ms 10716 KB Output is correct
4 Correct 45 ms 11132 KB Output is correct
5 Correct 46 ms 11120 KB Output is correct
6 Correct 39 ms 10604 KB Output is correct
7 Correct 34 ms 9548 KB Output is correct
8 Correct 127 ms 25216 KB Output is correct
9 Correct 117 ms 25300 KB Output is correct
10 Correct 36 ms 9568 KB Output is correct
11 Correct 489 ms 42052 KB Output is correct
12 Correct 512 ms 41960 KB Output is correct
13 Correct 200 ms 42460 KB Output is correct
14 Correct 33 ms 9664 KB Output is correct
15 Correct 188 ms 34244 KB Output is correct
16 Correct 353 ms 33712 KB Output is correct
17 Correct 357 ms 40436 KB Output is correct
18 Correct 347 ms 39884 KB Output is correct
19 Correct 468 ms 43004 KB Output is correct
20 Correct 478 ms 42984 KB Output is correct
21 Correct 136 ms 26932 KB Output is correct
22 Correct 143 ms 27080 KB Output is correct
23 Correct 228 ms 35492 KB Output is correct
24 Correct 204 ms 34400 KB Output is correct
25 Correct 418 ms 41952 KB Output is correct
26 Correct 370 ms 38852 KB Output is correct
27 Correct 381 ms 39036 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 8644 KB Output is correct
2 Correct 46 ms 10984 KB Output is correct
3 Correct 41 ms 10716 KB Output is correct
4 Correct 45 ms 11132 KB Output is correct
5 Correct 46 ms 11120 KB Output is correct
6 Correct 39 ms 10604 KB Output is correct
7 Correct 34 ms 9548 KB Output is correct
8 Correct 127 ms 25216 KB Output is correct
9 Correct 117 ms 25300 KB Output is correct
10 Correct 36 ms 9568 KB Output is correct
11 Correct 489 ms 42052 KB Output is correct
12 Correct 512 ms 41960 KB Output is correct
13 Correct 200 ms 42460 KB Output is correct
14 Correct 33 ms 9664 KB Output is correct
15 Correct 188 ms 34244 KB Output is correct
16 Correct 353 ms 33712 KB Output is correct
17 Correct 357 ms 40436 KB Output is correct
18 Correct 347 ms 39884 KB Output is correct
19 Correct 468 ms 43004 KB Output is correct
20 Correct 478 ms 42984 KB Output is correct
21 Correct 136 ms 26932 KB Output is correct
22 Correct 143 ms 27080 KB Output is correct
23 Correct 228 ms 35492 KB Output is correct
24 Correct 204 ms 34400 KB Output is correct
25 Correct 418 ms 41952 KB Output is correct
26 Correct 370 ms 38852 KB Output is correct
27 Correct 381 ms 39036 KB Output is correct
28 Incorrect 35 ms 9572 KB Extra information in the output file
29 Halted 0 ms 0 KB -