oj.uz

Submission #140845

# Submission time Handle Problem Language Result Execution time Memory
140845 2019-08-05T15:40:52 Z andrew Werewolf (IOI18_werewolf) C++17
100 / 100
 959 ms 81780 KB 
#include <bits/stdc++.h>
#include "werewolf.h"

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
const ll N = 2e5 + 1;

template <typename T> void vout(T s){cout << s << endl;exit(0);}

vector <int> v[N];

int tin[N + 1], tout[N + 1], stn;
int tin1[N + 1], tout1[N + 1], stn1;

vector <int> Up[N], Down[N];

int t[4 * N], pos[N], p[N], pt[N];

void dfs(int x, int p){
    tin[x] = ++stn;
    for(int to : Up[x])if(to != p)dfs(to, x);
    tout[x] = stn;
}


void go(int x, int p){
    tin1[x] = ++stn1;
    pos[tin1[x]] = tin[x];
    pt[tin[x]] = tin1[x];
    for(int to : Down[x])if(to != p)go(to, x);
    tout1[x] = stn1;
}


void build(int v, int tl, int tr){
    if(tl == tr)t[v] = pos[tl]; else{
        int tm = (tl + tr) >> 1;
        build(v << 1, tl, tm);
        build((v << 1) + 1, tm + 1, tr);
        t[v] = min(t[v << 1], t[(v << 1) + 1]);
    }
}

void modify(int v, int tl, int tr, int pos){
    if(tl == tr)t[v] = 1e9; else{
        int tm = (tl + tr) >> 1;
        if(pos <= tm)modify(v << 1, tl, tm, pos);
        else modify((v << 1) + 1, tm + 1, tr, pos);
        t[v] = min(t[v << 1], t[(v << 1) + 1]);
    }
}

int get(int v, int tl, int tr, int l, int r){
    if(l > r)return 1e9;
    if(tl == l && tr == r)return t[v];
    int tm = (tl + tr) >> 1;
    return min(get(v << 1, tl, tm, l, min(r, tm)), get((v << 1) + 1, tm + 1, tr, max(l, tm + 1), r));
}

int get(int x){
    if(p[x] != x)p[x] = get(p[x]);
    return p[x];
}

vector <int> vq[N];

vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r){
    int q = s.size(), m = x.size();

    vi ans(q);

    for(int &i : x)i++;
    for(int &i : y)i++;
    for(int &i : s)i++;
    for(int &i : e)i++;
    for(int &i : l)i++;
    for(int &i : r)i++;

    for(int i = 0; i < m; i++){
        v[x[i]].p_b(y[i]);
        v[y[i]].p_b(x[i]);
    }

    for(int i = 0; i < q; i++)vq[l[i]].p_b(i);

    for(int i = 1; i <= n; i++)p[i] = i;

    int old;

    for(int i = n; i > 0; i--){
        for(int j : v[i])if(j > i){
            if(get(j) != i){
                old = get(j);
                p[get(j)] = i;
                Up[old].p_b(i);
                Up[i].p_b(old);
            }
        }
        for(int j : vq[i]){
            l[j] = get(s[j]);
        }
        vq[i].clear();
    }

    for(int i = 1; i <= n; i++)p[i] = i;
    for(int i = 0; i < q; i++)vq[r[i]].p_b(i);

    for(int i = 1; i <= n; i++){
        for(int j : v[i])if(j < i){
            if(get(j) != i){
                old = get(j);
                p[get(j)] = i;
                Down[old].p_b(i);
                Down[i].p_b(old);
            }
        }

        for(int j : vq[i]){
            r[j] = get(e[j]);
        }
        vq[i].clear();
    }

    dfs(1ll, 0ll);
    go(n, 0ll);

    build(1, 1, n);

    vector <pii> Q;

    for(int i = 0; i < q; i++){
        if(s[i] < l[i])continue;
        if(e[i] > r[i])continue;
        Q.p_b({tin[l[i]], i});
    }

    if(Q.empty())return ans;

    sort(all(Q));

    int uk = 1;

    for(pii kek : Q){
        while(uk < kek.fi){
            modify(1, 1, n, pt[uk++]);
        }
        if(get(1, 1, n, tin1[r[kek.se]], tout1[r[kek.se]]) <= tout[l[kek.se]])ans[kek.se] = 1;

    }

    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19320 KB Output is correct
2 Correct 19 ms 19192 KB Output is correct
3 Correct 19 ms 19092 KB Output is correct
4 Correct 20 ms 19192 KB Output is correct
5 Correct 19 ms 19192 KB Output is correct
6 Correct 20 ms 19192 KB Output is correct
7 Correct 19 ms 19192 KB Output is correct
8 Correct 20 ms 19192 KB Output is correct
9 Correct 19 ms 19192 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19320 KB Output is correct
2 Correct 19 ms 19192 KB Output is correct
3 Correct 19 ms 19092 KB Output is correct
4 Correct 20 ms 19192 KB Output is correct
5 Correct 19 ms 19192 KB Output is correct
6 Correct 20 ms 19192 KB Output is correct
7 Correct 19 ms 19192 KB Output is correct
8 Correct 20 ms 19192 KB Output is correct
9 Correct 19 ms 19192 KB Output is correct
10 Correct 26 ms 20088 KB Output is correct
11 Correct 28 ms 20088 KB Output is correct
12 Correct 26 ms 19960 KB Output is correct
13 Correct 26 ms 20088 KB Output is correct
14 Correct 26 ms 20088 KB Output is correct
15 Correct 27 ms 20088 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 881 ms 71772 KB Output is correct
2 Correct 774 ms 75116 KB Output is correct
3 Correct 838 ms 73068 KB Output is correct
4 Correct 834 ms 72044 KB Output is correct
5 Correct 815 ms 72028 KB Output is correct
6 Correct 846 ms 71788 KB Output is correct
7 Correct 789 ms 70156 KB Output is correct
8 Correct 741 ms 75116 KB Output is correct
9 Correct 667 ms 72300 KB Output is correct
10 Correct 638 ms 71532 KB Output is correct
11 Correct 693 ms 71544 KB Output is correct
12 Correct 765 ms 71748 KB Output is correct
13 Correct 750 ms 76524 KB Output is correct
14 Correct 750 ms 76396 KB Output is correct
15 Correct 724 ms 76396 KB Output is correct
16 Correct 728 ms 76444 KB Output is correct
17 Correct 770 ms 70252 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19320 KB Output is correct
2 Correct 19 ms 19192 KB Output is correct
3 Correct 19 ms 19092 KB Output is correct
4 Correct 20 ms 19192 KB Output is correct
5 Correct 19 ms 19192 KB Output is correct
6 Correct 20 ms 19192 KB Output is correct
7 Correct 19 ms 19192 KB Output is correct
8 Correct 20 ms 19192 KB Output is correct
9 Correct 19 ms 19192 KB Output is correct
10 Correct 26 ms 20088 KB Output is correct
11 Correct 28 ms 20088 KB Output is correct
12 Correct 26 ms 19960 KB Output is correct
13 Correct 26 ms 20088 KB Output is correct
14 Correct 26 ms 20088 KB Output is correct
15 Correct 27 ms 20088 KB Output is correct
16 Correct 881 ms 71772 KB Output is correct
17 Correct 774 ms 75116 KB Output is correct
18 Correct 838 ms 73068 KB Output is correct
19 Correct 834 ms 72044 KB Output is correct
20 Correct 815 ms 72028 KB Output is correct
21 Correct 846 ms 71788 KB Output is correct
22 Correct 789 ms 70156 KB Output is correct
23 Correct 741 ms 75116 KB Output is correct
24 Correct 667 ms 72300 KB Output is correct
25 Correct 638 ms 71532 KB Output is correct
26 Correct 693 ms 71544 KB Output is correct
27 Correct 765 ms 71748 KB Output is correct
28 Correct 750 ms 76524 KB Output is correct
29 Correct 750 ms 76396 KB Output is correct
30 Correct 724 ms 76396 KB Output is correct
31 Correct 728 ms 76444 KB Output is correct
32 Correct 770 ms 70252 KB Output is correct
33 Correct 945 ms 73068 KB Output is correct
34 Correct 396 ms 54352 KB Output is correct
35 Correct 890 ms 75496 KB Output is correct
36 Correct 885 ms 72428 KB Output is correct
37 Correct 959 ms 74872 KB Output is correct
38 Correct 896 ms 73056 KB Output is correct
39 Correct 854 ms 81780 KB Output is correct
40 Correct 910 ms 79584 KB Output is correct
41 Correct 850 ms 74260 KB Output is correct
42 Correct 753 ms 72048 KB Output is correct
43 Correct 927 ms 79340 KB Output is correct
44 Correct 862 ms 74732 KB Output is correct
45 Correct 787 ms 81416 KB Output is correct
46 Correct 741 ms 81224 KB Output is correct
47 Correct 763 ms 76692 KB Output is correct
48 Correct 747 ms 76652 KB Output is correct
49 Correct 720 ms 76572 KB Output is correct
50 Correct 727 ms 76368 KB Output is correct
51 Correct 841 ms 78320 KB Output is correct
52 Correct 837 ms 78328 KB Output is correct