oj.uz

Submission #555807

# Submission time Handle Problem Language Result Execution time Memory
555807 2022-05-01T15:01:38 Z cheissmart Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 176492 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e6 + 7;

int p1[N], jump1[N], time1[N], l1[N], r1[N];
int st1[N][20];
vi T1[N];

int find1(int u) {
    return jump1[u] == u ? u : jump1[u] = find1(jump1[u]);
}

int p2[N], jump2[N], time2[N], l2[N], r2[N];
vi T2[N];
int st2[N][20];
int find2(int u) {
    return jump2[u] == u ? u : jump2[u] = find2(jump2[u]);
}

vi check_validity(int n, vi a, vi b, vi S, vi E, vi L, vi R) {
    int m = SZ(a), q = SZ(S);
    V<vi> G(n);
    for(int i = 0; i < m; i++) {
        G[a[i]].PB(b[i]);
        G[b[i]].PB(a[i]);
    }
    int rt1, rt2;
    {
        int cnt = n;
        for(int i = 0; i < n; i++) {
            time1[i] = jump1[i] = p1[i] = i;
            for(int j:G[i]) if(j < i) {
                int x = find1(j), y = find1(i);
                if(x == y) continue;
                jump1[x] = jump1[y] = p1[x] = p1[y] = cnt;
                T1[cnt].PB(x), T1[cnt].PB(y);
                p1[cnt] = jump1[cnt] = cnt;
                time1[cnt] = i;
                cnt++;
            }
        }
        rt1 = cnt - 1;
        for(int i = 0; i < cnt; i++)
            st1[i][0] = p1[i];
        for(int j = 1; j < 20; j++)
            for(int i = 0; i < cnt; i++)
                st1[i][j] = st1[st1[i][j - 1]][j - 1];
    }
    {
        int cnt = n;
        for(int i = n - 1; i >= 0; i--) {
            time2[i] = jump2[i] = p2[i] = i;
            for(int j:G[i]) if(j > i) {
                int x = find2(j), y = find2(i);
                if(x == y) continue;
                jump2[x] = jump2[y] = p2[x] = p2[y] = cnt;
                T2[cnt].PB(x), T2[cnt].PB(y);
                p2[cnt] = jump2[cnt] = cnt;
                time2[cnt] = i;
                cnt++;
            }
        }
        rt2 = cnt - 1;
        for(int i = 0; i < cnt; i++)
            st2[i][0] = p2[i];
        for(int j = 1; j < 20; j++)
            for(int i = 0; i < cnt; i++)
                st2[i][j] = st2[st2[i][j - 1]][j - 1];
    }

    vi order1;
    {
        function<void(int)> dfs = [&] (int u) {
            l1[u] = SZ(order1);
            if(T1[u].empty()) {
                assert(0 <= u && u < n);
                order1.PB(u);
            }
            for(int v:T1[u])
                dfs(v);
            r1[u] = SZ(order1);
        };
        dfs(rt1);
    }
    vi pos(n);
    for(int i = 0; i < n; i++)
        pos[order1[i]] = i;

    vi order2;
    {
        function<void(int)> dfs = [&] (int u) {
            l2[u] = SZ(order2);
            if(T2[u].empty()) {
                assert(0 <= u && u < n);
                order2.PB(pos[u]);
            }
            for(int v:T2[u])
                dfs(v);
            r2[u] = SZ(order2);
        };
        dfs(rt2);
    }
    vi ans(q);
    for(int i = 0; i < q; i++) {
        int e = E[i], s = S[i], l = L[i], r = R[i];
        for(int j = 19; j >= 0; j--) {
            if(time1[st1[e][j]] <= r) {
                e = st1[e][j];
            }
        }
        for(int j = 19; j >= 0; j--) {
            if(time2[st2[s][j]] >= l) {
                s = st2[s][j];
            }
        }
        int lb = l1[e], rb = r1[e];
        for(int j = l2[s]; j < r2[s]; j++) {
            if(lb <= order2[j] && order2[j] < rb) {
                ans[i] = 1;
                break;
            }
        }
        // [l1[e], r1[e]) of order1
        // [l2[s], r2[s]) of order2

    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47392 KB Output is correct
2 Correct 24 ms 47340 KB Output is correct
3 Correct 23 ms 47368 KB Output is correct
4 Correct 23 ms 47316 KB Output is correct
5 Correct 24 ms 47424 KB Output is correct
6 Correct 23 ms 47336 KB Output is correct
7 Correct 23 ms 47304 KB Output is correct
8 Correct 24 ms 47420 KB Output is correct
9 Correct 29 ms 47408 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47392 KB Output is correct
2 Correct 24 ms 47340 KB Output is correct
3 Correct 23 ms 47368 KB Output is correct
4 Correct 23 ms 47316 KB Output is correct
5 Correct 24 ms 47424 KB Output is correct
6 Correct 23 ms 47336 KB Output is correct
7 Correct 23 ms 47304 KB Output is correct
8 Correct 24 ms 47420 KB Output is correct
9 Correct 29 ms 47408 KB Output is correct
10 Correct 30 ms 49096 KB Output is correct
11 Correct 30 ms 49256 KB Output is correct
12 Correct 33 ms 49040 KB Output is correct
13 Correct 31 ms 49224 KB Output is correct
14 Correct 35 ms 49224 KB Output is correct
15 Correct 41 ms 49100 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 806 ms 161820 KB Output is correct
2 Correct 718 ms 176492 KB Output is correct
3 Correct 798 ms 172452 KB Output is correct
4 Correct 2789 ms 170732 KB Output is correct
5 Correct 3080 ms 170672 KB Output is correct
6 Correct 737 ms 170528 KB Output is correct
7 Execution timed out 4048 ms 170116 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47392 KB Output is correct
2 Correct 24 ms 47340 KB Output is correct
3 Correct 23 ms 47368 KB Output is correct
4 Correct 23 ms 47316 KB Output is correct
5 Correct 24 ms 47424 KB Output is correct
6 Correct 23 ms 47336 KB Output is correct
7 Correct 23 ms 47304 KB Output is correct
8 Correct 24 ms 47420 KB Output is correct
9 Correct 29 ms 47408 KB Output is correct
10 Correct 30 ms 49096 KB Output is correct
11 Correct 30 ms 49256 KB Output is correct
12 Correct 33 ms 49040 KB Output is correct
13 Correct 31 ms 49224 KB Output is correct
14 Correct 35 ms 49224 KB Output is correct
15 Correct 41 ms 49100 KB Output is correct
16 Correct 806 ms 161820 KB Output is correct
17 Correct 718 ms 176492 KB Output is correct
18 Correct 798 ms 172452 KB Output is correct
19 Correct 2789 ms 170732 KB Output is correct
20 Correct 3080 ms 170672 KB Output is correct
21 Correct 737 ms 170528 KB Output is correct
22 Execution timed out 4048 ms 170116 KB Time limit exceeded
23 Halted 0 ms 0 KB -