oj.uz

Submission #81140

# Submission time Handle Problem Language Result Execution time Memory
81140 2018-10-24T02:20:17 Z cki86201 Werewolf (IOI18_werewolf) C++11
100 / 100
 1047 ms 425572 KB 
#include "werewolf.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

struct tree {
    vector <int> F[200020];
    int lv[200020], rv[200020], cs = 0;
    int up[200020][18];
    void addE(int x, int y) {   // x <- y
        F[x].pb(y);
    }
    void dfs(int x) {
        lv[x] = ++cs;
        for(int e : F[x]) {
            up[e][0] = x;
            for(int i=1;i<18;i++) {
                up[e][i] = up[ up[e][i-1] ][i-1];
            }
            dfs(e);
        }
        rv[x] = cs;
    }
    pii get_seg_g(int x, int l) {
        for(int i=17;i>=0;i--) {
            if(up[x][i] && up[x][i] >= l) x = up[x][i];
        }
        return pii(lv[x], rv[x]);
    }
    pii get_seg_l(int x, int r) {
        for(int i=17;i>=0;i--) {
            if(up[x][i] && up[x][i] <= r) x = up[x][i];
        }
        return pii(lv[x], rv[x]);
    }
} T[2];

int pp[200020]; int Find(int x) { return pp[x] == x ? x : pp[x] = Find(pp[x]); }
int val[200020];
vector <int> EE[200010];
int N;

vector <t3> pquery[200020];
int TT[200020];
int cnt[200020];

void pre_query(int idx, int S, int E, int L, int R) {
    pii p1 = T[0].get_seg_l(E, R);
    pii p2 = T[1].get_seg_g(S, L);
    pquery[p1.Se].pb(t3(p2.Se, idx, 1));
    pquery[p1.Se].pb(t3(p2.Fi-1, idx, -1));
    pquery[p1.Fi-1].pb(t3(p2.Se, idx, -1));
    pquery[p1.Fi-1].pb(t3(p2.Fi-1, idx, 1));
}

std::vector<int> check_validity(int nn, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    N = nn;
    int M = szz(X);
    for(int i=0;i<M;i++) {
        int x = X[i] + 1, y = Y[i] + 1;
        EE[x].pb(y);
        EE[y].pb(x);
    }
    for(int i=1;i<=N;i++) pp[i] = i;
    for(int i=1;i<=N;i++) {
        for(int e : EE[i]) if(e < i) {
            int x = Find(i), y = Find(e);
            if(x == y) continue;
            pp[y] = x;
            T[0].addE(x, y);
        }
    }
    for(int i=1;i<=N;i++) pp[i] = i;
    for(int i=N;i;i--) {
        for(int e : EE[i]) if(e > i) {
            int x = Find(i), y = Find(e);
            if(x == y) continue;
            pp[y] = x;
            T[1].addE(x, y);
        }
    }
    T[0].dfs(N); T[1].dfs(1);
    for(int i=1;i<=N;i++) {
        val[T[0].lv[i]] = T[1].lv[i];
    }
    int Q = szz(S);
    rep(i, Q) {
        ++S[i]; ++E[i]; ++L[i]; ++R[i];
        pre_query(i, S[i], E[i], L[i], R[i]);
    }
    for(int i=1;i<=N;i++) {
        int x = val[i];
        for(int j=x;j<200020;j+=(j&-j)) TT[j]++;
        for(t3 e : pquery[i]) {
            int y, idx, cc;
            tie(y, idx, cc) = e;
            int s = 0;
            for(int j=y;j;j-=(j&-j)) s += TT[j];
            cnt[idx] += cc * s;
        }
    }
    vector <int> A(Q);
    rep(i, Q) {
        A[i] = cnt[i] > 0 ? 1 : 0;
    }
    return A;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19192 KB Output is correct
2 Correct 21 ms 19356 KB Output is correct
3 Correct 19 ms 19460 KB Output is correct
4 Correct 18 ms 19460 KB Output is correct
5 Correct 20 ms 19496 KB Output is correct
6 Correct 19 ms 19496 KB Output is correct
7 Correct 19 ms 19496 KB Output is correct
8 Correct 19 ms 19556 KB Output is correct
9 Correct 19 ms 19556 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19192 KB Output is correct
2 Correct 21 ms 19356 KB Output is correct
3 Correct 19 ms 19460 KB Output is correct
4 Correct 18 ms 19460 KB Output is correct
5 Correct 20 ms 19496 KB Output is correct
6 Correct 19 ms 19496 KB Output is correct
7 Correct 19 ms 19496 KB Output is correct
8 Correct 19 ms 19556 KB Output is correct
9 Correct 19 ms 19556 KB Output is correct
10 Correct 28 ms 20808 KB Output is correct
11 Correct 26 ms 20916 KB Output is correct
12 Correct 30 ms 21016 KB Output is correct
13 Correct 27 ms 21344 KB Output is correct
14 Correct 26 ms 21344 KB Output is correct
15 Correct 29 ms 21448 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 879 ms 101460 KB Output is correct
2 Correct 830 ms 112564 KB Output is correct
3 Correct 726 ms 119704 KB Output is correct
4 Correct 697 ms 126604 KB Output is correct
5 Correct 707 ms 134768 KB Output is correct
6 Correct 736 ms 142968 KB Output is correct
7 Correct 756 ms 149256 KB Output is correct
8 Correct 901 ms 162968 KB Output is correct
9 Correct 674 ms 169968 KB Output is correct
10 Correct 572 ms 175532 KB Output is correct
11 Correct 609 ms 185364 KB Output is correct
12 Correct 605 ms 193152 KB Output is correct
13 Correct 859 ms 207596 KB Output is correct
14 Correct 883 ms 216056 KB Output is correct
15 Correct 931 ms 224636 KB Output is correct
16 Correct 899 ms 232856 KB Output is correct
17 Correct 764 ms 233208 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19192 KB Output is correct
2 Correct 21 ms 19356 KB Output is correct
3 Correct 19 ms 19460 KB Output is correct
4 Correct 18 ms 19460 KB Output is correct
5 Correct 20 ms 19496 KB Output is correct
6 Correct 19 ms 19496 KB Output is correct
7 Correct 19 ms 19496 KB Output is correct
8 Correct 19 ms 19556 KB Output is correct
9 Correct 19 ms 19556 KB Output is correct
10 Correct 28 ms 20808 KB Output is correct
11 Correct 26 ms 20916 KB Output is correct
12 Correct 30 ms 21016 KB Output is correct
13 Correct 27 ms 21344 KB Output is correct
14 Correct 26 ms 21344 KB Output is correct
15 Correct 29 ms 21448 KB Output is correct
16 Correct 879 ms 101460 KB Output is correct
17 Correct 830 ms 112564 KB Output is correct
18 Correct 726 ms 119704 KB Output is correct
19 Correct 697 ms 126604 KB Output is correct
20 Correct 707 ms 134768 KB Output is correct
21 Correct 736 ms 142968 KB Output is correct
22 Correct 756 ms 149256 KB Output is correct
23 Correct 901 ms 162968 KB Output is correct
24 Correct 674 ms 169968 KB Output is correct
25 Correct 572 ms 175532 KB Output is correct
26 Correct 609 ms 185364 KB Output is correct
27 Correct 605 ms 193152 KB Output is correct
28 Correct 859 ms 207596 KB Output is correct
29 Correct 883 ms 216056 KB Output is correct
30 Correct 931 ms 224636 KB Output is correct
31 Correct 899 ms 232856 KB Output is correct
32 Correct 764 ms 233208 KB Output is correct
33 Correct 887 ms 244756 KB Output is correct
34 Correct 449 ms 244756 KB Output is correct
35 Correct 986 ms 266952 KB Output is correct
36 Correct 902 ms 274016 KB Output is correct
37 Correct 1047 ms 283536 KB Output is correct
38 Correct 832 ms 291372 KB Output is correct
39 Correct 848 ms 304456 KB Output is correct
40 Correct 1018 ms 314952 KB Output is correct
41 Correct 737 ms 318432 KB Output is correct
42 Correct 679 ms 326668 KB Output is correct
43 Correct 1014 ms 343072 KB Output is correct
44 Correct 844 ms 347696 KB Output is correct
45 Correct 805 ms 360448 KB Output is correct
46 Correct 786 ms 368572 KB Output is correct
47 Correct 918 ms 377012 KB Output is correct
48 Correct 859 ms 385276 KB Output is correct
49 Correct 895 ms 393820 KB Output is correct
50 Correct 894 ms 402188 KB Output is correct
51 Correct 921 ms 413904 KB Output is correct
52 Correct 898 ms 425572 KB Output is correct