oj.uz

Submission #529487

# Submission time Handle Problem Language Result Execution time Memory
529487 2022-02-23T04:37:59 Z qwerasdfzxcl Inside information (BOI21_servers) C++14
100 / 100
 490 ms 43152 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]];
            if (god[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 8640 KB Output is correct
2 Correct 43 ms 9540 KB Output is correct
3 Correct 40 ms 9388 KB Output is correct
4 Correct 46 ms 9756 KB Output is correct
5 Correct 42 ms 9668 KB Output is correct
6 Correct 40 ms 9256 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8640 KB Output is correct
2 Correct 43 ms 9540 KB Output is correct
3 Correct 40 ms 9388 KB Output is correct
4 Correct 46 ms 9756 KB Output is correct
5 Correct 42 ms 9668 KB Output is correct
6 Correct 40 ms 9256 KB Output is correct
7 Correct 35 ms 8708 KB Output is correct
8 Correct 44 ms 10624 KB Output is correct
9 Correct 44 ms 10436 KB Output is correct
10 Correct 53 ms 10724 KB Output is correct
11 Correct 44 ms 10740 KB Output is correct
12 Correct 39 ms 10352 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 8616 KB Output is correct
2 Correct 140 ms 22500 KB Output is correct
3 Correct 124 ms 22456 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 8616 KB Output is correct
2 Correct 140 ms 22500 KB Output is correct
3 Correct 124 ms 22456 KB Output is correct
4 Correct 34 ms 8604 KB Output is correct
5 Correct 137 ms 22436 KB Output is correct
6 Correct 111 ms 22680 KB Output is correct
7 Correct 110 ms 22632 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8680 KB Output is correct
2 Correct 315 ms 38656 KB Output is correct
3 Correct 266 ms 38756 KB Output is correct
4 Correct 186 ms 39236 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8680 KB Output is correct
2 Correct 315 ms 38656 KB Output is correct
3 Correct 266 ms 38756 KB Output is correct
4 Correct 186 ms 39236 KB Output is correct
5 Correct 35 ms 8648 KB Output is correct
6 Correct 300 ms 41576 KB Output is correct
7 Correct 221 ms 42348 KB Output is correct
8 Correct 314 ms 41152 KB Output is correct
9 Correct 292 ms 41096 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8728 KB Output is correct
2 Correct 205 ms 30932 KB Output is correct
3 Correct 233 ms 30456 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8728 KB Output is correct
2 Correct 205 ms 30932 KB Output is correct
3 Correct 233 ms 30456 KB Output is correct
4 Correct 34 ms 8704 KB Output is correct
5 Correct 194 ms 33864 KB Output is correct
6 Correct 273 ms 33260 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 8776 KB Output is correct
2 Correct 277 ms 38652 KB Output is correct
3 Correct 327 ms 38732 KB Output is correct
4 Correct 193 ms 39272 KB Output is correct
5 Correct 33 ms 8712 KB Output is correct
6 Correct 167 ms 31044 KB Output is correct
7 Correct 240 ms 30424 KB Output is correct
8 Correct 273 ms 37204 KB Output is correct
9 Correct 276 ms 36720 KB Output is correct
10 Correct 325 ms 39600 KB Output is correct
11 Correct 315 ms 39620 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 8776 KB Output is correct
2 Correct 277 ms 38652 KB Output is correct
3 Correct 327 ms 38732 KB Output is correct
4 Correct 193 ms 39272 KB Output is correct
5 Correct 33 ms 8712 KB Output is correct
6 Correct 167 ms 31044 KB Output is correct
7 Correct 240 ms 30424 KB Output is correct
8 Correct 273 ms 37204 KB Output is correct
9 Correct 276 ms 36720 KB Output is correct
10 Correct 325 ms 39600 KB Output is correct
11 Correct 315 ms 39620 KB Output is correct
12 Correct 34 ms 8780 KB Output is correct
13 Correct 325 ms 41556 KB Output is correct
14 Correct 211 ms 42204 KB Output is correct
15 Correct 306 ms 41104 KB Output is correct
16 Correct 297 ms 41176 KB Output is correct
17 Correct 44 ms 9584 KB Output is correct
18 Correct 213 ms 33964 KB Output is correct
19 Correct 300 ms 33376 KB Output is correct
20 Correct 288 ms 40392 KB Output is correct
21 Correct 318 ms 39996 KB Output is correct
22 Correct 338 ms 42140 KB Output is correct
23 Correct 490 ms 42792 KB Output is correct
24 Correct 439 ms 43152 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8644 KB Output is correct
2 Correct 59 ms 9564 KB Output is correct
3 Correct 41 ms 9336 KB Output is correct
4 Correct 44 ms 9668 KB Output is correct
5 Correct 47 ms 9652 KB Output is correct
6 Correct 40 ms 9308 KB Output is correct
7 Correct 32 ms 8648 KB Output is correct
8 Correct 124 ms 22476 KB Output is correct
9 Correct 122 ms 22456 KB Output is correct
10 Correct 34 ms 8772 KB Output is correct
11 Correct 292 ms 38704 KB Output is correct
12 Correct 276 ms 38732 KB Output is correct
13 Correct 188 ms 39196 KB Output is correct
14 Correct 37 ms 8748 KB Output is correct
15 Correct 163 ms 31100 KB Output is correct
16 Correct 290 ms 30468 KB Output is correct
17 Correct 269 ms 37208 KB Output is correct
18 Correct 289 ms 36716 KB Output is correct
19 Correct 347 ms 39640 KB Output is correct
20 Correct 394 ms 39624 KB Output is correct
21 Correct 133 ms 23632 KB Output is correct
22 Correct 148 ms 23592 KB Output is correct
23 Correct 204 ms 32172 KB Output is correct
24 Correct 185 ms 31132 KB Output is correct
25 Correct 396 ms 38596 KB Output is correct
26 Correct 279 ms 35396 KB Output is correct
27 Correct 312 ms 35544 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8644 KB Output is correct
2 Correct 59 ms 9564 KB Output is correct
3 Correct 41 ms 9336 KB Output is correct
4 Correct 44 ms 9668 KB Output is correct
5 Correct 47 ms 9652 KB Output is correct
6 Correct 40 ms 9308 KB Output is correct
7 Correct 32 ms 8648 KB Output is correct
8 Correct 124 ms 22476 KB Output is correct
9 Correct 122 ms 22456 KB Output is correct
10 Correct 34 ms 8772 KB Output is correct
11 Correct 292 ms 38704 KB Output is correct
12 Correct 276 ms 38732 KB Output is correct
13 Correct 188 ms 39196 KB Output is correct
14 Correct 37 ms 8748 KB Output is correct
15 Correct 163 ms 31100 KB Output is correct
16 Correct 290 ms 30468 KB Output is correct
17 Correct 269 ms 37208 KB Output is correct
18 Correct 289 ms 36716 KB Output is correct
19 Correct 347 ms 39640 KB Output is correct
20 Correct 394 ms 39624 KB Output is correct
21 Correct 133 ms 23632 KB Output is correct
22 Correct 148 ms 23592 KB Output is correct
23 Correct 204 ms 32172 KB Output is correct
24 Correct 185 ms 31132 KB Output is correct
25 Correct 396 ms 38596 KB Output is correct
26 Correct 279 ms 35396 KB Output is correct
27 Correct 312 ms 35544 KB Output is correct
28 Correct 33 ms 8732 KB Output is correct
29 Correct 44 ms 10564 KB Output is correct
30 Correct 42 ms 10416 KB Output is correct
31 Correct 47 ms 10792 KB Output is correct
32 Correct 45 ms 10696 KB Output is correct
33 Correct 41 ms 10348 KB Output is correct
34 Correct 34 ms 9540 KB Output is correct
35 Correct 141 ms 25108 KB Output is correct
36 Correct 108 ms 24420 KB Output is correct
37 Correct 112 ms 24500 KB Output is correct
38 Correct 35 ms 9540 KB Output is correct
39 Correct 290 ms 41528 KB Output is correct
40 Correct 226 ms 42220 KB Output is correct
41 Correct 304 ms 41076 KB Output is correct
42 Correct 360 ms 41192 KB Output is correct
43 Correct 40 ms 9664 KB Output is correct
44 Correct 194 ms 33960 KB Output is correct
45 Correct 274 ms 33240 KB Output is correct
46 Correct 296 ms 40404 KB Output is correct
47 Correct 318 ms 39876 KB Output is correct
48 Correct 372 ms 42196 KB Output is correct
49 Correct 487 ms 42872 KB Output is correct
50 Correct 423 ms 43076 KB Output is correct
51 Correct 134 ms 26760 KB Output is correct
52 Correct 120 ms 26036 KB Output is correct
53 Correct 115 ms 25096 KB Output is correct
54 Correct 123 ms 25996 KB Output is correct
55 Correct 155 ms 26448 KB Output is correct
56 Correct 203 ms 35240 KB Output is correct
57 Correct 296 ms 41520 KB Output is correct
58 Correct 324 ms 38920 KB Output is correct
59 Correct 304 ms 38744 KB Output is correct