oj.uz

Submission #401790

# Submission time Handle Problem Language Result Execution time Memory
401790 2021-05-10T20:11:32 Z gevacrt Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 150004 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>

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 = 120010;
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 {
    __gnu_pbds::gp_hash_table<int, int> arr;

    void add(int x, int val){ x++;
        for(; x < 2*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(2*MAXN-1);}
    int order_of_key(int x){return query(x-1);}
} jp[MAXN];

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

    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 76 ms 48068 KB Output is correct
2 Correct 94 ms 49808 KB Output is correct
3 Correct 156 ms 49488 KB Output is correct
4 Correct 92 ms 49720 KB Output is correct
5 Correct 127 ms 50100 KB Output is correct
6 Correct 165 ms 49060 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 76 ms 48068 KB Output is correct
2 Correct 94 ms 49808 KB Output is correct
3 Correct 156 ms 49488 KB Output is correct
4 Correct 92 ms 49720 KB Output is correct
5 Correct 127 ms 50100 KB Output is correct
6 Correct 165 ms 49060 KB Output is correct
7 Correct 88 ms 48180 KB Output is correct
8 Correct 156 ms 51828 KB Output is correct
9 Correct 186 ms 49720 KB Output is correct
10 Correct 164 ms 51632 KB Output is correct
11 Correct 333 ms 52516 KB Output is correct
12 Correct 148 ms 49224 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 91 ms 48192 KB Output is correct
2 Correct 544 ms 68180 KB Output is correct
3 Correct 547 ms 68156 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 91 ms 48192 KB Output is correct
2 Correct 544 ms 68180 KB Output is correct
3 Correct 547 ms 68156 KB Output is correct
4 Correct 99 ms 48212 KB Output is correct
5 Correct 532 ms 68180 KB Output is correct
6 Correct 362 ms 68428 KB Output is correct
7 Correct 386 ms 68284 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 48068 KB Output is correct
2 Correct 1035 ms 107308 KB Output is correct
3 Correct 1006 ms 107352 KB Output is correct
4 Correct 1878 ms 128120 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 48068 KB Output is correct
2 Correct 1035 ms 107308 KB Output is correct
3 Correct 1006 ms 107352 KB Output is correct
4 Correct 1878 ms 128120 KB Output is correct
5 Correct 79 ms 48156 KB Output is correct
6 Correct 1180 ms 129828 KB Output is correct
7 Correct 2178 ms 149900 KB Output is correct
8 Correct 1283 ms 141716 KB Output is correct
9 Correct 1288 ms 141680 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 48168 KB Output is correct
2 Correct 1391 ms 113832 KB Output is correct
3 Correct 1133 ms 106168 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 48168 KB Output is correct
2 Correct 1391 ms 113832 KB Output is correct
3 Correct 1133 ms 106168 KB Output is correct
4 Correct 82 ms 48160 KB Output is correct
5 Correct 1976 ms 141992 KB Output is correct
6 Correct 1427 ms 137200 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 72 ms 48216 KB Output is correct
2 Correct 1030 ms 107452 KB Output is correct
3 Correct 1008 ms 107484 KB Output is correct
4 Correct 1868 ms 128216 KB Output is correct
5 Correct 76 ms 48280 KB Output is correct
6 Correct 1394 ms 113660 KB Output is correct
7 Correct 1129 ms 106452 KB Output is correct
8 Correct 1126 ms 103048 KB Output is correct
9 Correct 1134 ms 102072 KB Output is correct
10 Correct 1595 ms 110888 KB Output is correct
11 Correct 1561 ms 111672 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 72 ms 48216 KB Output is correct
2 Correct 1030 ms 107452 KB Output is correct
3 Correct 1008 ms 107484 KB Output is correct
4 Correct 1868 ms 128216 KB Output is correct
5 Correct 76 ms 48280 KB Output is correct
6 Correct 1394 ms 113660 KB Output is correct
7 Correct 1129 ms 106452 KB Output is correct
8 Correct 1126 ms 103048 KB Output is correct
9 Correct 1134 ms 102072 KB Output is correct
10 Correct 1595 ms 110888 KB Output is correct
11 Correct 1561 ms 111672 KB Output is correct
12 Correct 79 ms 48172 KB Output is correct
13 Correct 1186 ms 129624 KB Output is correct
14 Correct 2192 ms 150004 KB Output is correct
15 Correct 1291 ms 141756 KB Output is correct
16 Correct 1300 ms 141788 KB Output is correct
17 Correct 86 ms 48208 KB Output is correct
18 Correct 1967 ms 141976 KB Output is correct
19 Correct 1419 ms 137272 KB Output is correct
20 Correct 1604 ms 135768 KB Output is correct
21 Correct 1341 ms 119208 KB Output is correct
22 Correct 2296 ms 144564 KB Output is correct
23 Execution timed out 3584 ms 148248 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 76 ms 48068 KB Output is correct
2 Correct 94 ms 49820 KB Output is correct
3 Correct 162 ms 49596 KB Output is correct
4 Correct 91 ms 49732 KB Output is correct
5 Correct 128 ms 50076 KB Output is correct
6 Correct 165 ms 49152 KB Output is correct
7 Correct 92 ms 48176 KB Output is correct
8 Correct 553 ms 68112 KB Output is correct
9 Correct 544 ms 68044 KB Output is correct
10 Correct 71 ms 48068 KB Output is correct
11 Correct 1014 ms 107380 KB Output is correct
12 Correct 1006 ms 107404 KB Output is correct
13 Correct 1866 ms 128320 KB Output is correct
14 Correct 76 ms 48064 KB Output is correct
15 Correct 1412 ms 113896 KB Output is correct
16 Correct 1144 ms 106280 KB Output is correct
17 Correct 1110 ms 103180 KB Output is correct
18 Correct 1127 ms 101944 KB Output is correct
19 Correct 1600 ms 110940 KB Output is correct
20 Correct 1570 ms 111472 KB Output is correct
21 Correct 638 ms 73160 KB Output is correct
22 Correct 602 ms 71068 KB Output is correct
23 Correct 948 ms 85432 KB Output is correct
24 Correct 961 ms 85708 KB Output is correct
25 Correct 1035 ms 90004 KB Output is correct
26 Correct 878 ms 94280 KB Output is correct
27 Correct 751 ms 93752 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 76 ms 48068 KB Output is correct
2 Correct 94 ms 49820 KB Output is correct
3 Correct 162 ms 49596 KB Output is correct
4 Correct 91 ms 49732 KB Output is correct
5 Correct 128 ms 50076 KB Output is correct
6 Correct 165 ms 49152 KB Output is correct
7 Correct 92 ms 48176 KB Output is correct
8 Correct 553 ms 68112 KB Output is correct
9 Correct 544 ms 68044 KB Output is correct
10 Correct 71 ms 48068 KB Output is correct
11 Correct 1014 ms 107380 KB Output is correct
12 Correct 1006 ms 107404 KB Output is correct
13 Correct 1866 ms 128320 KB Output is correct
14 Correct 76 ms 48064 KB Output is correct
15 Correct 1412 ms 113896 KB Output is correct
16 Correct 1144 ms 106280 KB Output is correct
17 Correct 1110 ms 103180 KB Output is correct
18 Correct 1127 ms 101944 KB Output is correct
19 Correct 1600 ms 110940 KB Output is correct
20 Correct 1570 ms 111472 KB Output is correct
21 Correct 638 ms 73160 KB Output is correct
22 Correct 602 ms 71068 KB Output is correct
23 Correct 948 ms 85432 KB Output is correct
24 Correct 961 ms 85708 KB Output is correct
25 Correct 1035 ms 90004 KB Output is correct
26 Correct 878 ms 94280 KB Output is correct
27 Correct 751 ms 93752 KB Output is correct
28 Correct 88 ms 48084 KB Output is correct
29 Correct 159 ms 51880 KB Output is correct
30 Correct 185 ms 49596 KB Output is correct
31 Correct 160 ms 51828 KB Output is correct
32 Correct 337 ms 52372 KB Output is correct
33 Correct 149 ms 49104 KB Output is correct
34 Correct 99 ms 48164 KB Output is correct
35 Correct 552 ms 68172 KB Output is correct
36 Correct 359 ms 68424 KB Output is correct
37 Correct 373 ms 68172 KB Output is correct
38 Correct 81 ms 48068 KB Output is correct
39 Correct 1175 ms 129896 KB Output is correct
40 Correct 2199 ms 149928 KB Output is correct
41 Correct 1296 ms 141712 KB Output is correct
42 Correct 1294 ms 141728 KB Output is correct
43 Correct 83 ms 48192 KB Output is correct
44 Correct 1990 ms 141780 KB Output is correct
45 Correct 1416 ms 137152 KB Output is correct
46 Correct 1693 ms 135544 KB Output is correct
47 Correct 1462 ms 119124 KB Output is correct
48 Correct 2452 ms 144592 KB Output is correct
49 Execution timed out 3538 ms 141128 KB Time limit exceeded
50 Halted 0 ms 0 KB -