oj.uz

Submission #401765

# Submission time Handle Problem Language Result Execution time Memory
401765 2021-05-10T19:28:43 Z gevacrt Inside information (BOI21_servers) C++17
50 / 100
 1955 ms 137184 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 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;
    }
};

struct PBDS {
    gp_hash_table<int, int> arr;

    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;
    } 
    void insert(int x){add(x, 1);};
    void erase(int x){add(x, -1);};
    
    int size(){return query(MAXN);}
    int order_of_key(int x){return query(x-1);}
};

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

    PBDS 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 51 ms 22724 KB Output is correct
2 Correct 68 ms 25232 KB Output is correct
3 Correct 142 ms 24888 KB Output is correct
4 Correct 65 ms 25156 KB Output is correct
5 Correct 102 ms 25184 KB Output is correct
6 Correct 158 ms 24516 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 22724 KB Output is correct
2 Correct 68 ms 25232 KB Output is correct
3 Correct 142 ms 24888 KB Output is correct
4 Correct 65 ms 25156 KB Output is correct
5 Correct 102 ms 25184 KB Output is correct
6 Correct 158 ms 24516 KB Output is correct
7 Correct 64 ms 22796 KB Output is correct
8 Incorrect 142 ms 27420 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 22816 KB Output is correct
2 Correct 599 ms 66516 KB Output is correct
3 Correct 600 ms 66808 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 22816 KB Output is correct
2 Correct 599 ms 66516 KB Output is correct
3 Correct 600 ms 66808 KB Output is correct
4 Correct 71 ms 22824 KB Output is correct
5 Incorrect 561 ms 66540 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22796 KB Output is correct
2 Correct 939 ms 80836 KB Output is correct
3 Correct 953 ms 80756 KB Output is correct
4 Correct 1798 ms 111512 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22796 KB Output is correct
2 Correct 939 ms 80836 KB Output is correct
3 Correct 953 ms 80756 KB Output is correct
4 Correct 1798 ms 111512 KB Output is correct
5 Correct 54 ms 22796 KB Output is correct
6 Incorrect 1145 ms 105500 KB Extra information in the output file
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 22756 KB Output is correct
2 Correct 1380 ms 107572 KB Output is correct
3 Correct 1116 ms 90144 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 22756 KB Output is correct
2 Correct 1380 ms 107572 KB Output is correct
3 Correct 1116 ms 90144 KB Output is correct
4 Correct 58 ms 22940 KB Output is correct
5 Incorrect 1955 ms 137184 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22724 KB Output is correct
2 Correct 955 ms 80880 KB Output is correct
3 Correct 979 ms 80808 KB Output is correct
4 Correct 1786 ms 111456 KB Output is correct
5 Correct 51 ms 22804 KB Output is correct
6 Correct 1440 ms 107556 KB Output is correct
7 Correct 1091 ms 90244 KB Output is correct
8 Correct 1155 ms 96880 KB Output is correct
9 Correct 1146 ms 82240 KB Output is correct
10 Correct 1517 ms 94524 KB Output is correct
11 Correct 1540 ms 101052 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22724 KB Output is correct
2 Correct 955 ms 80880 KB Output is correct
3 Correct 979 ms 80808 KB Output is correct
4 Correct 1786 ms 111456 KB Output is correct
5 Correct 51 ms 22804 KB Output is correct
6 Correct 1440 ms 107556 KB Output is correct
7 Correct 1091 ms 90244 KB Output is correct
8 Correct 1155 ms 96880 KB Output is correct
9 Correct 1146 ms 82240 KB Output is correct
10 Correct 1517 ms 94524 KB Output is correct
11 Correct 1540 ms 101052 KB Output is correct
12 Correct 64 ms 22800 KB Output is correct
13 Incorrect 1145 ms 105600 KB Extra information in the output file
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 22812 KB Output is correct
2 Correct 69 ms 25140 KB Output is correct
3 Correct 130 ms 24952 KB Output is correct
4 Correct 67 ms 25060 KB Output is correct
5 Correct 111 ms 25164 KB Output is correct
6 Correct 141 ms 24552 KB Output is correct
7 Correct 69 ms 22756 KB Output is correct
8 Correct 628 ms 66588 KB Output is correct
9 Correct 570 ms 66596 KB Output is correct
10 Correct 46 ms 22812 KB Output is correct
11 Correct 963 ms 80872 KB Output is correct
12 Correct 1012 ms 80824 KB Output is correct
13 Correct 1845 ms 111572 KB Output is correct
14 Correct 49 ms 22816 KB Output is correct
15 Correct 1404 ms 107648 KB Output is correct
16 Correct 1147 ms 90180 KB Output is correct
17 Correct 1143 ms 97052 KB Output is correct
18 Correct 1130 ms 82376 KB Output is correct
19 Correct 1509 ms 94532 KB Output is correct
20 Correct 1594 ms 101128 KB Output is correct
21 Correct 668 ms 69940 KB Output is correct
22 Correct 628 ms 68500 KB Output is correct
23 Correct 928 ms 77096 KB Output is correct
24 Correct 918 ms 77280 KB Output is correct
25 Correct 1094 ms 75616 KB Output is correct
26 Correct 876 ms 89948 KB Output is correct
27 Correct 771 ms 91884 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 22812 KB Output is correct
2 Correct 69 ms 25140 KB Output is correct
3 Correct 130 ms 24952 KB Output is correct
4 Correct 67 ms 25060 KB Output is correct
5 Correct 111 ms 25164 KB Output is correct
6 Correct 141 ms 24552 KB Output is correct
7 Correct 69 ms 22756 KB Output is correct
8 Correct 628 ms 66588 KB Output is correct
9 Correct 570 ms 66596 KB Output is correct
10 Correct 46 ms 22812 KB Output is correct
11 Correct 963 ms 80872 KB Output is correct
12 Correct 1012 ms 80824 KB Output is correct
13 Correct 1845 ms 111572 KB Output is correct
14 Correct 49 ms 22816 KB Output is correct
15 Correct 1404 ms 107648 KB Output is correct
16 Correct 1147 ms 90180 KB Output is correct
17 Correct 1143 ms 97052 KB Output is correct
18 Correct 1130 ms 82376 KB Output is correct
19 Correct 1509 ms 94532 KB Output is correct
20 Correct 1594 ms 101128 KB Output is correct
21 Correct 668 ms 69940 KB Output is correct
22 Correct 628 ms 68500 KB Output is correct
23 Correct 928 ms 77096 KB Output is correct
24 Correct 918 ms 77280 KB Output is correct
25 Correct 1094 ms 75616 KB Output is correct
26 Correct 876 ms 89948 KB Output is correct
27 Correct 771 ms 91884 KB Output is correct
28 Correct 63 ms 22764 KB Output is correct
29 Incorrect 131 ms 27184 KB Extra information in the output file
30 Halted 0 ms 0 KB -