oj.uz

Submission #401333

# Submission time Handle Problem Language Result Execution time Memory
401333 2021-05-09T21:16:12 Z Osama_Alkhodairy Werewolf (IOI18_werewolf) C++17
100 / 100
 882 ms 121720 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
//~ #include "grader.cpp"
using namespace std;

const int N = 400001;

struct dsu{
    int n, p[N], l[N], r[N], t;
    vector <int> v[N], perm;
    void resize(int _n){
        n = _n;
        t = 0;
        for(int i = 0 ; i < 2 * n ; i++){
            p[i] = i;
        }
    }
    int find(int x){
        if(p[x] == x) return x;
        return p[x] = find(p[x]);
    }
    void merge(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return;
        v[n].push_back(x);
        v[n].push_back(y);
        p[x] = n;
        p[y] = n;
        n++;
    }
    void dfs(int node){
        perm.push_back(node);
        l[node] = t++;
        for(auto &i : v[node]){
            dfs(i);
        }
        r[node] = t - 1;
    }
    void dfs(){
        dfs(n - 1);
    }
};

struct segment{
    int n, tree[2 * N];
    void resize(int _n){
        n = _n;
    }
    void update(int p, int v){
        for(tree[p += n] = v ; p > 1 ; p >>= 1){
            tree[p >> 1] = tree[p] + tree[p ^ 1];
        }
    }
    int query(int l, int r){
        r++;
        int ret = 0;
        for(l += n, r += n ; l < r ; l >>= 1, r >>= 1){
            if(l & 1) ret += tree[l++];
            if(r & 1) ret += tree[--r];
        }
        return ret;
    }
};

vector <int> v[N], g[N];
vector <pair <int, int> > q, h[N];
dsu a, b;
segment tree;

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
    a.resize(N);
    b.resize(N);
    int M = X.size(), Q = S.size();
    for(int i = 0 ; i < M ; i++){
        v[X[i]].push_back(Y[i]);
        v[Y[i]].push_back(X[i]);
    }
    q.resize(S.size());
    for(int i = 0 ; i < Q ; i++){
        g[L[i]].push_back(i);
    }
    for(int i = N - 1 ; i >= 0 ; i--){
        for(auto &j : v[i]){
            if(j > i){
                a.merge(i, j);
            }
        }
        for(auto &j : g[i]){
            q[j].first = a.find(S[j]);
        }
        g[i].clear();
    }
    for(int i = 0 ; i < Q ; i++){
        g[R[i]].push_back(i);
    }
    for(int i = 0 ; i < N ; i++){
        for(auto &j : v[i]){
            if(j < i){
                b.merge(i, j);
            }
        }
        for(auto &j : g[i]){
            q[j].second = b.find(E[j]);
        }
        g[i].clear();
    }
    a.dfs();
    b.dfs();
    vector <int> pos(2 * N - 1);
    for(int i = 0 ; i < 2 * N - 1 ; i++){
        pos[b.perm[i]] = i;
    }
    tree.resize(2 * N - 1);
    for(int i = 0 ; i < Q ; i++){
        h[a.r[q[i].first]].push_back(make_pair(i, 1));
        if(a.l[q[i].first] > 0){
            h[a.l[q[i].first] - 1].push_back(make_pair(i, -1));
        }
    }
    vector <int> ans(Q);
    for(int i = 0 ; i < 2 * N - 1 ; i++){
        if(a.perm[i] < N) tree.update(pos[a.perm[i]], 1);
        for(auto &j : h[i]){
            ans[j.first] += tree.query(b.l[q[j.first].second], b.r[q[j.first].second]) * j.second;
        }
    }
    for(auto &i : ans) i = i > 0;
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47308 KB Output is correct
2 Correct 31 ms 47236 KB Output is correct
3 Correct 30 ms 47208 KB Output is correct
4 Correct 30 ms 47216 KB Output is correct
5 Correct 30 ms 47308 KB Output is correct
6 Correct 30 ms 47340 KB Output is correct
7 Correct 31 ms 47252 KB Output is correct
8 Correct 31 ms 47328 KB Output is correct
9 Correct 35 ms 47344 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47308 KB Output is correct
2 Correct 31 ms 47236 KB Output is correct
3 Correct 30 ms 47208 KB Output is correct
4 Correct 30 ms 47216 KB Output is correct
5 Correct 30 ms 47308 KB Output is correct
6 Correct 30 ms 47340 KB Output is correct
7 Correct 31 ms 47252 KB Output is correct
8 Correct 31 ms 47328 KB Output is correct
9 Correct 35 ms 47344 KB Output is correct
10 Correct 37 ms 48268 KB Output is correct
11 Correct 37 ms 48244 KB Output is correct
12 Correct 35 ms 48152 KB Output is correct
13 Correct 41 ms 48280 KB Output is correct
14 Correct 36 ms 48232 KB Output is correct
15 Correct 36 ms 48164 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 106328 KB Output is correct
2 Correct 708 ms 110076 KB Output is correct
3 Correct 681 ms 106744 KB Output is correct
4 Correct 707 ms 105204 KB Output is correct
5 Correct 674 ms 105300 KB Output is correct
6 Correct 727 ms 106160 KB Output is correct
7 Correct 635 ms 103704 KB Output is correct
8 Correct 663 ms 109872 KB Output is correct
9 Correct 580 ms 104896 KB Output is correct
10 Correct 570 ms 104276 KB Output is correct
11 Correct 553 ms 104460 KB Output is correct
12 Correct 612 ms 104544 KB Output is correct
13 Correct 653 ms 110268 KB Output is correct
14 Correct 719 ms 110228 KB Output is correct
15 Correct 674 ms 110236 KB Output is correct
16 Correct 677 ms 110324 KB Output is correct
17 Correct 645 ms 103548 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47308 KB Output is correct
2 Correct 31 ms 47236 KB Output is correct
3 Correct 30 ms 47208 KB Output is correct
4 Correct 30 ms 47216 KB Output is correct
5 Correct 30 ms 47308 KB Output is correct
6 Correct 30 ms 47340 KB Output is correct
7 Correct 31 ms 47252 KB Output is correct
8 Correct 31 ms 47328 KB Output is correct
9 Correct 35 ms 47344 KB Output is correct
10 Correct 37 ms 48268 KB Output is correct
11 Correct 37 ms 48244 KB Output is correct
12 Correct 35 ms 48152 KB Output is correct
13 Correct 41 ms 48280 KB Output is correct
14 Correct 36 ms 48232 KB Output is correct
15 Correct 36 ms 48164 KB Output is correct
16 Correct 788 ms 106328 KB Output is correct
17 Correct 708 ms 110076 KB Output is correct
18 Correct 681 ms 106744 KB Output is correct
19 Correct 707 ms 105204 KB Output is correct
20 Correct 674 ms 105300 KB Output is correct
21 Correct 727 ms 106160 KB Output is correct
22 Correct 635 ms 103704 KB Output is correct
23 Correct 663 ms 109872 KB Output is correct
24 Correct 580 ms 104896 KB Output is correct
25 Correct 570 ms 104276 KB Output is correct
26 Correct 553 ms 104460 KB Output is correct
27 Correct 612 ms 104544 KB Output is correct
28 Correct 653 ms 110268 KB Output is correct
29 Correct 719 ms 110228 KB Output is correct
30 Correct 674 ms 110236 KB Output is correct
31 Correct 677 ms 110324 KB Output is correct
32 Correct 645 ms 103548 KB Output is correct
33 Correct 882 ms 107932 KB Output is correct
34 Correct 358 ms 79728 KB Output is correct
35 Correct 828 ms 116532 KB Output is correct
36 Correct 760 ms 112816 KB Output is correct
37 Correct 823 ms 115684 KB Output is correct
38 Correct 805 ms 113384 KB Output is correct
39 Correct 784 ms 121720 KB Output is correct
40 Correct 772 ms 113896 KB Output is correct
41 Correct 704 ms 113644 KB Output is correct
42 Correct 602 ms 109984 KB Output is correct
43 Correct 827 ms 117628 KB Output is correct
44 Correct 724 ms 114720 KB Output is correct
45 Correct 665 ms 119664 KB Output is correct
46 Correct 695 ms 119640 KB Output is correct
47 Correct 673 ms 115744 KB Output is correct
48 Correct 673 ms 115588 KB Output is correct
49 Correct 701 ms 115684 KB Output is correct
50 Correct 657 ms 115536 KB Output is correct
51 Correct 650 ms 112180 KB Output is correct
52 Correct 663 ms 112308 KB Output is correct