oj.uz

Submission #401760

# Submission time Handle Problem Language Result Execution time Memory
401760 2021-05-10T19:18:13 Z gevacrt Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 138772 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;

typedef tree<int,null_type,less_equal<int>,rb_tree_tag,
    tree_order_statistics_node_update> ordered_set;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

const int MAXN = 12e4+10;
vvi adj(MAXN); vi depth(MAXN);

namespace DSU {
    vi par(MAXN), sz(MAXN);
    void init(){
        for(int x = 0; x < MAXN; x++)
            par[x] = x, sz[x] = 1;
    }
    
    int parent(int x){
        if(par[x] == x) return x;
        return par[x] = parent(par[x]);
    }

    void merge(int x, int y){
        x = parent(x), y = parent(y);
        if(x == y) return;
        par[x] = y; sz[y] += sz[x];
    }
};

namespace LCA {
    int timer = 0;
    vi tin(MAXN), tout(MAXN);
    vvi par(MAXN, vi(20));

    void dfs(int u, int p, int h){
        depth[u] = h;
        
        par[u][0] = p;
        for(int i = 1; i < 20; i++)
            par[u][i] = par[par[u][i-1]][i-1];

        tin[u] = timer++;
        for(auto v : adj[u])
            if(v != p) dfs(v, u, h+1);
        tout[u] = timer-1;
    }
    // Is u an ancestor of v?
    bool isAncestor(int u, int v){
        return tin[u] <= tin[v] and
            tout[v] <= tout[u];
    }

    int query(int u, int v){
        if(isAncestor(u, v)) return u;
        if(isAncestor(v, u)) return v;
        for(int i = 19; i >= 0; i--)
            if(!isAncestor(par[u][i], v))
                u = par[u][i];
        return par[u][0];
    }

    int query1(int u, int v){
        for(int i = 19; i >= 0; i--)
            if(!isAncestor(par[v][i], u))
                v = par[v][i];
        return v;
    }

    void init(){
        dfs(0, 0, 1);
    }
};

namespace BIT {
    vi arr(MAXN);
    void add(int x, int val){ x++;
        for(; x < MAXN; x += x&(-x))
            arr[x] += val;
    }
    int query(int x){ x++;
        int ans = 0;
        for(; x > 0; x -= x&(-x))
            ans += arr[x];
        return ans;
    }
};

namespace CD {
    unordered_set<int> pres;
    vi par(MAXN), cnt(MAXN);

    int dfs(int u, int p){
        cnt[u] = 1;
        for(auto v : adj[u])
            if(v != p and !pres.count(v))
                cnt[u] += dfs(v, u);
        return cnt[u];
    }
    int dfs(int u, int p, int sz){
        for(auto v : adj[u])
            if(v != p and !pres.count(v))
                if(cnt[v] > sz/2) return dfs(v, u, sz);
        return u;
    }

    void build(int u, int p){
        int sz = dfs(u,u), ct = dfs(u,u,sz);
        par[ct] = p; pres.insert(ct);
        for(auto v : adj[ct])
            if(!pres.count(v)) build(v, ct);
    }
    void init(){
        build(0, -1);
    }
};

bool inc(int u, int v){
    int p = LCA::query1(u, v);
    auto f = BIT::query(LCA::tin[v])-BIT::query(LCA::tin[p]);
    if(f == depth[v]-depth[p]) return true;
    return false;
}

bool dec(int u, int v){
    int p = LCA::query1(u, v);
    auto f = BIT::query(LCA::tin[v])-BIT::query(LCA::tin[p]);
    if(f == 0) return true;
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K; cin >> N >> K;
    
    vector<array<int, 3>> Q(N+K-1);
    for(int x = 0; x < N+K-1; x++){
        char c; cin >> c;
        if(c == 'S'){
            int u, v; cin >> u >> v;
            u--, v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
            Q[x] = {0, u, v};
        }else if(c == 'Q'){
            int u, d; cin >> u >> d;
            u--, d--;
            Q[x] = {1, d, u};
        }else{
            int d; cin >> d;
            Q[x] = {2, --d, d};
        }
    }

    LCA::init(); DSU::init(); CD::init();

    vi isConnected(N);
    auto path_exists = [&](int u, int v)->bool{
        if(DSU::parent(u) != DSU::parent(v))
            return false;

        int p = LCA::query(u, v);

        if(p == u){
            if(inc(u, v)) return true;
        }else if(p == v){
            if(dec(v, u)) return true;
        }else{
            int p1 = LCA::query1(p, u), p2 = LCA::query1(p, v);

            if(dec(p, u) and inc(p, v) and isConnected[p1] < isConnected[p2])
                return true;
        }
        return false;        
    };

    ordered_set jp[N]; set<ii> mc;
    auto uupp = [&](int u){
        for(int p = CD::par[u]; p != -1; p = CD::par[p]){
            if(!path_exists(p, u)) continue;
            if(mc.count({u, p})) continue;
            mc.insert({u, p});

            int p1;
            if(LCA::query(p, u) == p){
                p1 = LCA::query1(p, u);
            }else p1 = p;

            jp[p].insert(isConnected[p1]);
        }
    };

    for(uint x = 0; x < Q.size(); x++){
        if(Q[x][0] == 0){
            int u = Q[x][1], v = Q[x][2];
            if(depth[u] > depth[v]) swap(u, v);

            if(isConnected[u])
                BIT::add(LCA::tin[v], 1),
                BIT::add(LCA::tout[v]+1, -1);

            DSU::merge(u, v);
            isConnected[v] = x+1;

            uupp(u); uupp(v);

        }else if(Q[x][0] == 1){
            int u = Q[x][1], v = Q[x][2];
            if(path_exists(u, v)) cout << "yes\n";
            else cout << "no\n";
        
        }else{
            int u = Q[x][1], ans = 0;
            
            for(int p = u; p != -1; p = CD::par[p]){
                if(p != u and !path_exists(u, p)) continue;
                
                ans++;
                if(p == u){
                    ans += jp[u].size();
                }else if(LCA::query(u, p) == p){
                    int p1 = LCA::query1(p, u);
                    ans += jp[p].size()-jp[p].order_of_key(isConnected[p1]+1);
                } else{
                    ans += jp[p].size()-jp[p].order_of_key(isConnected[p]+1);
                }
            }

            // int ans1 = 0;
            // for(int v = 0; v < N; v++)
            //     if(v == u or path_exists(u, v)) ans1++;
            // assert(ans1 == ans);

            cout << ans << "\n";
        }
    }

    return 0;
}
/*
5 2
S 1 2
S 4 5
S 3 4
C 2
S 2 3
C 2
*/

Compilation message

servers.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
servers.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 22724 KB Output is correct
2 Correct 67 ms 25368 KB Output is correct
3 Correct 129 ms 25380 KB Output is correct
4 Correct 64 ms 25372 KB Output is correct
5 Correct 98 ms 25360 KB Output is correct
6 Correct 140 ms 25276 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 22724 KB Output is correct
2 Correct 67 ms 25368 KB Output is correct
3 Correct 129 ms 25380 KB Output is correct
4 Correct 64 ms 25372 KB Output is correct
5 Correct 98 ms 25360 KB Output is correct
6 Correct 140 ms 25276 KB Output is correct
7 Correct 56 ms 23592 KB Output is correct
8 Correct 98 ms 25124 KB Output is correct
9 Correct 137 ms 25176 KB Output is correct
10 Correct 99 ms 24960 KB Output is correct
11 Correct 249 ms 25148 KB Output is correct
12 Correct 117 ms 25024 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 22812 KB Output is correct
2 Correct 677 ms 57472 KB Output is correct
3 Correct 662 ms 57472 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 22812 KB Output is correct
2 Correct 677 ms 57472 KB Output is correct
3 Correct 662 ms 57472 KB Output is correct
4 Correct 69 ms 23684 KB Output is correct
5 Correct 636 ms 57392 KB Output is correct
6 Correct 460 ms 56660 KB Output is correct
7 Correct 477 ms 56920 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22728 KB Output is correct
2 Correct 900 ms 65432 KB Output is correct
3 Correct 878 ms 65576 KB Output is correct
4 Correct 2134 ms 138628 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22728 KB Output is correct
2 Correct 900 ms 65432 KB Output is correct
3 Correct 878 ms 65576 KB Output is correct
4 Correct 2134 ms 138628 KB Output is correct
5 Correct 51 ms 23572 KB Output is correct
6 Correct 920 ms 65092 KB Output is correct
7 Correct 2247 ms 134236 KB Output is correct
8 Correct 936 ms 64580 KB Output is correct
9 Correct 924 ms 64440 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 22700 KB Output is correct
2 Correct 1701 ms 123336 KB Output is correct
3 Correct 1014 ms 65716 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 22700 KB Output is correct
2 Correct 1701 ms 123336 KB Output is correct
3 Correct 1014 ms 65716 KB Output is correct
4 Correct 54 ms 23580 KB Output is correct
5 Correct 1964 ms 123168 KB Output is correct
6 Correct 1134 ms 65232 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22664 KB Output is correct
2 Correct 869 ms 65440 KB Output is correct
3 Correct 873 ms 65440 KB Output is correct
4 Correct 2120 ms 138612 KB Output is correct
5 Correct 49 ms 23672 KB Output is correct
6 Correct 1706 ms 123352 KB Output is correct
7 Correct 1026 ms 65608 KB Output is correct
8 Correct 1101 ms 64484 KB Output is correct
9 Correct 1115 ms 64468 KB Output is correct
10 Correct 1631 ms 90404 KB Output is correct
11 Correct 1594 ms 90564 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22664 KB Output is correct
2 Correct 869 ms 65440 KB Output is correct
3 Correct 873 ms 65440 KB Output is correct
4 Correct 2120 ms 138612 KB Output is correct
5 Correct 49 ms 23672 KB Output is correct
6 Correct 1706 ms 123352 KB Output is correct
7 Correct 1026 ms 65608 KB Output is correct
8 Correct 1101 ms 64484 KB Output is correct
9 Correct 1115 ms 64468 KB Output is correct
10 Correct 1631 ms 90404 KB Output is correct
11 Correct 1594 ms 90564 KB Output is correct
12 Correct 50 ms 23648 KB Output is correct
13 Correct 912 ms 65016 KB Output is correct
14 Correct 2220 ms 134308 KB Output is correct
15 Correct 937 ms 64700 KB Output is correct
16 Correct 919 ms 64444 KB Output is correct
17 Correct 53 ms 23580 KB Output is correct
18 Correct 1947 ms 123208 KB Output is correct
19 Correct 1128 ms 65204 KB Output is correct
20 Correct 1352 ms 64244 KB Output is correct
21 Correct 1129 ms 64068 KB Output is correct
22 Correct 2059 ms 89564 KB Output is correct
23 Execution timed out 3563 ms 111364 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 22740 KB Output is correct
2 Correct 67 ms 25408 KB Output is correct
3 Correct 128 ms 25380 KB Output is correct
4 Correct 62 ms 25284 KB Output is correct
5 Correct 103 ms 25516 KB Output is correct
6 Correct 140 ms 25160 KB Output is correct
7 Correct 67 ms 23692 KB Output is correct
8 Correct 674 ms 57512 KB Output is correct
9 Correct 679 ms 57484 KB Output is correct
10 Correct 46 ms 23620 KB Output is correct
11 Correct 876 ms 65388 KB Output is correct
12 Correct 881 ms 65448 KB Output is correct
13 Correct 2127 ms 138772 KB Output is correct
14 Correct 50 ms 23620 KB Output is correct
15 Correct 1698 ms 123356 KB Output is correct
16 Correct 1028 ms 65732 KB Output is correct
17 Correct 1061 ms 64460 KB Output is correct
18 Correct 1096 ms 64696 KB Output is correct
19 Correct 1633 ms 90420 KB Output is correct
20 Correct 1593 ms 90424 KB Output is correct
21 Correct 751 ms 61920 KB Output is correct
22 Correct 723 ms 60388 KB Output is correct
23 Correct 1034 ms 65228 KB Output is correct
24 Correct 1045 ms 65640 KB Output is correct
25 Correct 1046 ms 62368 KB Output is correct
26 Correct 731 ms 59224 KB Output is correct
27 Correct 636 ms 58580 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 22740 KB Output is correct
2 Correct 67 ms 25408 KB Output is correct
3 Correct 128 ms 25380 KB Output is correct
4 Correct 62 ms 25284 KB Output is correct
5 Correct 103 ms 25516 KB Output is correct
6 Correct 140 ms 25160 KB Output is correct
7 Correct 67 ms 23692 KB Output is correct
8 Correct 674 ms 57512 KB Output is correct
9 Correct 679 ms 57484 KB Output is correct
10 Correct 46 ms 23620 KB Output is correct
11 Correct 876 ms 65388 KB Output is correct
12 Correct 881 ms 65448 KB Output is correct
13 Correct 2127 ms 138772 KB Output is correct
14 Correct 50 ms 23620 KB Output is correct
15 Correct 1698 ms 123356 KB Output is correct
16 Correct 1028 ms 65732 KB Output is correct
17 Correct 1061 ms 64460 KB Output is correct
18 Correct 1096 ms 64696 KB Output is correct
19 Correct 1633 ms 90420 KB Output is correct
20 Correct 1593 ms 90424 KB Output is correct
21 Correct 751 ms 61920 KB Output is correct
22 Correct 723 ms 60388 KB Output is correct
23 Correct 1034 ms 65228 KB Output is correct
24 Correct 1045 ms 65640 KB Output is correct
25 Correct 1046 ms 62368 KB Output is correct
26 Correct 731 ms 59224 KB Output is correct
27 Correct 636 ms 58580 KB Output is correct
28 Correct 56 ms 23588 KB Output is correct
29 Correct 97 ms 25120 KB Output is correct
30 Correct 136 ms 25160 KB Output is correct
31 Correct 99 ms 25028 KB Output is correct
32 Correct 248 ms 25120 KB Output is correct
33 Correct 118 ms 25024 KB Output is correct
34 Correct 69 ms 23576 KB Output is correct
35 Correct 642 ms 57436 KB Output is correct
36 Correct 459 ms 56660 KB Output is correct
37 Correct 489 ms 56916 KB Output is correct
38 Correct 52 ms 23560 KB Output is correct
39 Correct 923 ms 65072 KB Output is correct
40 Correct 2317 ms 134332 KB Output is correct
41 Correct 981 ms 64644 KB Output is correct
42 Correct 931 ms 64568 KB Output is correct
43 Correct 53 ms 23596 KB Output is correct
44 Correct 1953 ms 123048 KB Output is correct
45 Correct 1174 ms 65252 KB Output is correct
46 Correct 1368 ms 64036 KB Output is correct
47 Correct 1146 ms 64124 KB Output is correct
48 Correct 2055 ms 89768 KB Output is correct
49 Execution timed out 3529 ms 110624 KB Time limit exceeded
50 Halted 0 ms 0 KB -