oj.uz

Submission #262501

# Submission time Handle Problem Language Result Execution time Memory
262501 2020-08-13T02:00:54 Z yabsed Werewolf (IOI18_werewolf) C++17
100 / 100
 1133 ms 126984 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define MAXN 200005
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
 
int N, M, Q;
int djs[MAXN];
vector <int> con[MAXN];
 
// 아래에서부터 올라오는 트리 구조
int par[MAXN][18], num[MAXN], out[MAXN];
vector <int> child[MAXN];
 
// 위에서부터 내려가는 트리 구조
int par2[MAXN][18], num2[MAXN], out2[MAXN];
vector <int> child2[MAXN];
 
const int TS = 1<<19, ST = TS/2-1;
vector <int> tree[TS];
 
int find(int n){ return djs[n] == n ? n : (djs[n] = find(djs[n])); }
 
int K = 0;
void dfs(int n)
{
    num[n] = ++K;
    for (int t: child[n]) dfs(t);
    out[n] = K;
}
int K2 = 0;
void dfs2(int n)
{
    num2[n] = ++K2;
    for (int t: child2[n]) dfs2(t);
    out2[n] = K2;
}
 
bool is_exists(int l, int r, int mn, int mx)
{
    for (l+=ST,r+=ST;l<=r;l>>=1,r>>=1){
        if (l&1){
            auto it = lower_bound(all(tree[l]), mn);
            if (it != tree[l].end() && *it <= mx) return 1;
            l++;
        }
        if (~r&1){
            auto it = lower_bound(all(tree[r]), mn);
            if (it != tree[r].end() && *it <= mx) return 1;
            r--;
        }
    }
    return 0;
}
 
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
    ::N = N; ::M = sz(X); Q = sz(S);
    vector <int> ret(Q, 0);
    for (int i=0;i<M;i++){
        int a = ++X[i], b = ++Y[i];
        con[a].pb(b); con[b].pb(a);
    }
 
    for (int i=1;i<=N;i++) djs[i] = i;
    for (int i=1;i<=N;i++){
        for (int t: con[i]) if (t < i){
            if (find(t) != i){
                int m = find(t); djs[m] = i;
                par[m][0] = i; child[i].pb(m);
            }
        }
    }
    par[N][0] = N;
    for (int i=1;i<18;i++) for (int j=1;j<=N;j++) par[j][i] = par[par[j][i-1]][i-1];
    dfs(N);
 
    for (int i=1;i<=N;i++) djs[i] = i;
    for (int i=N;i;i--){
        for (int t: con[i]) if (t > i){
            if (find(t) != i){
                int m = find(t); djs[m] = i;
                par2[m][0] = i; child2[i].pb(m);
            }
        }
    }
    par2[1][0] = 1;
    for (int i=1;i<18;i++) for (int j=1;j<=N;j++) par2[j][i] = par2[par2[j][i-1]][i-1];
    dfs2(1);
 
    // Merge sort tree
    for (int i=1;i<=N;i++) tree[ST+num[i]].pb(num2[i]);
    for (int i=ST;i;i--){
        const auto &lc = tree[i+i], &rc = tree[i+i+1];
        for (int l=0,r=0;l<sz(lc)||r<sz(rc);){
            if (r == sz(rc) || l < sz(lc) && lc[l] < rc[r]) tree[i].pb(lc[l++]);
            else tree[i].pb(rc[r++]);
        }
    }
 
    for (int i=0;i<Q;i++){
        S[i]++; E[i]++; L[i]++; R[i]++;
        int n = E[i];
        for (int j=18;j--;) if (par[n][j] <= R[i]) n = par[n][j];
        int l = num[n], r = out[n];
 
        n = S[i];
        for (int j=18;j--;) if (par2[n][j] >= L[i]) n = par2[n][j];
        int mn = num2[n], mx = out2[n];
 
        ret[i] = is_exists(l, r, mn, mx);
    }
 
    return ret;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:98:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   98 |             if (r == sz(rc) || l < sz(lc) && lc[l] < rc[r]) tree[i].pb(lc[l++]);

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 26752 KB Output is correct
2 Correct 20 ms 26880 KB Output is correct
3 Correct 19 ms 26752 KB Output is correct
4 Correct 19 ms 26792 KB Output is correct
5 Correct 19 ms 26752 KB Output is correct
6 Correct 19 ms 26880 KB Output is correct
7 Correct 19 ms 26752 KB Output is correct
8 Correct 21 ms 26752 KB Output is correct
9 Correct 19 ms 26924 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 26752 KB Output is correct
2 Correct 20 ms 26880 KB Output is correct
3 Correct 19 ms 26752 KB Output is correct
4 Correct 19 ms 26792 KB Output is correct
5 Correct 19 ms 26752 KB Output is correct
6 Correct 19 ms 26880 KB Output is correct
7 Correct 19 ms 26752 KB Output is correct
8 Correct 21 ms 26752 KB Output is correct
9 Correct 19 ms 26924 KB Output is correct
10 Correct 26 ms 28152 KB Output is correct
11 Correct 26 ms 28160 KB Output is correct
12 Correct 26 ms 28160 KB Output is correct
13 Correct 27 ms 28288 KB Output is correct
14 Correct 27 ms 28416 KB Output is correct
15 Correct 28 ms 28288 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 895 ms 116852 KB Output is correct
2 Correct 798 ms 119376 KB Output is correct
3 Correct 755 ms 117936 KB Output is correct
4 Correct 834 ms 117056 KB Output is correct
5 Correct 883 ms 117056 KB Output is correct
6 Correct 932 ms 116896 KB Output is correct
7 Correct 842 ms 116800 KB Output is correct
8 Correct 757 ms 119232 KB Output is correct
9 Correct 834 ms 117568 KB Output is correct
10 Correct 644 ms 116928 KB Output is correct
11 Correct 652 ms 117060 KB Output is correct
12 Correct 820 ms 117040 KB Output is correct
13 Correct 946 ms 124224 KB Output is correct
14 Correct 961 ms 124148 KB Output is correct
15 Correct 966 ms 124128 KB Output is correct
16 Correct 963 ms 124188 KB Output is correct
17 Correct 861 ms 117008 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 26752 KB Output is correct
2 Correct 20 ms 26880 KB Output is correct
3 Correct 19 ms 26752 KB Output is correct
4 Correct 19 ms 26792 KB Output is correct
5 Correct 19 ms 26752 KB Output is correct
6 Correct 19 ms 26880 KB Output is correct
7 Correct 19 ms 26752 KB Output is correct
8 Correct 21 ms 26752 KB Output is correct
9 Correct 19 ms 26924 KB Output is correct
10 Correct 26 ms 28152 KB Output is correct
11 Correct 26 ms 28160 KB Output is correct
12 Correct 26 ms 28160 KB Output is correct
13 Correct 27 ms 28288 KB Output is correct
14 Correct 27 ms 28416 KB Output is correct
15 Correct 28 ms 28288 KB Output is correct
16 Correct 895 ms 116852 KB Output is correct
17 Correct 798 ms 119376 KB Output is correct
18 Correct 755 ms 117936 KB Output is correct
19 Correct 834 ms 117056 KB Output is correct
20 Correct 883 ms 117056 KB Output is correct
21 Correct 932 ms 116896 KB Output is correct
22 Correct 842 ms 116800 KB Output is correct
23 Correct 757 ms 119232 KB Output is correct
24 Correct 834 ms 117568 KB Output is correct
25 Correct 644 ms 116928 KB Output is correct
26 Correct 652 ms 117060 KB Output is correct
27 Correct 820 ms 117040 KB Output is correct
28 Correct 946 ms 124224 KB Output is correct
29 Correct 961 ms 124148 KB Output is correct
30 Correct 966 ms 124128 KB Output is correct
31 Correct 963 ms 124188 KB Output is correct
32 Correct 861 ms 117008 KB Output is correct
33 Correct 1123 ms 117056 KB Output is correct
34 Correct 420 ms 58360 KB Output is correct
35 Correct 1051 ms 119232 KB Output is correct
36 Correct 925 ms 117380 KB Output is correct
37 Correct 1054 ms 118576 KB Output is correct
38 Correct 974 ms 118024 KB Output is correct
39 Correct 1133 ms 124512 KB Output is correct
40 Correct 1125 ms 126984 KB Output is correct
41 Correct 922 ms 117952 KB Output is correct
42 Correct 734 ms 117456 KB Output is correct
43 Correct 1014 ms 123952 KB Output is correct
44 Correct 1000 ms 118524 KB Output is correct
45 Correct 882 ms 124964 KB Output is correct
46 Correct 869 ms 124592 KB Output is correct
47 Correct 942 ms 124352 KB Output is correct
48 Correct 973 ms 124156 KB Output is correct
49 Correct 1000 ms 124336 KB Output is correct
50 Correct 981 ms 124352 KB Output is correct
51 Correct 991 ms 126912 KB Output is correct
52 Correct 978 ms 126912 KB Output is correct