oj.uz

Submission #555804

# Submission time Handle Problem Language Result Execution time Memory
555804 2022-05-01T14:56:40 Z cheissmart Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 178700 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 order2;
    {
        function<void(int)> dfs = [&] (int u) {
            l2[u] = SZ(order2);
            if(T2[u].empty()) {
                assert(0 <= u && u < n);
                order2.PB(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];
            }
        }
        set<int> s1;
        for(int j = l1[e]; j < r1[e]; j++) {
            s1.insert(order1[j]);
        }
        for(int j = l2[s]; j < r2[s]; j++) {
            if(s1.count(order2[j])) {
                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 23 ms 47368 KB Output is correct
2 Correct 23 ms 47420 KB Output is correct
3 Correct 22 ms 47400 KB Output is correct
4 Correct 23 ms 47312 KB Output is correct
5 Correct 24 ms 47420 KB Output is correct
6 Correct 24 ms 47312 KB Output is correct
7 Correct 23 ms 47308 KB Output is correct
8 Correct 25 ms 47400 KB Output is correct
9 Correct 23 ms 47400 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47368 KB Output is correct
2 Correct 23 ms 47420 KB Output is correct
3 Correct 22 ms 47400 KB Output is correct
4 Correct 23 ms 47312 KB Output is correct
5 Correct 24 ms 47420 KB Output is correct
6 Correct 24 ms 47312 KB Output is correct
7 Correct 23 ms 47308 KB Output is correct
8 Correct 25 ms 47400 KB Output is correct
9 Correct 23 ms 47400 KB Output is correct
10 Correct 508 ms 49396 KB Output is correct
11 Correct 385 ms 49360 KB Output is correct
12 Correct 45 ms 49300 KB Output is correct
13 Correct 633 ms 49484 KB Output is correct
14 Correct 634 ms 49484 KB Output is correct
15 Correct 409 ms 49396 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4046 ms 178700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47368 KB Output is correct
2 Correct 23 ms 47420 KB Output is correct
3 Correct 22 ms 47400 KB Output is correct
4 Correct 23 ms 47312 KB Output is correct
5 Correct 24 ms 47420 KB Output is correct
6 Correct 24 ms 47312 KB Output is correct
7 Correct 23 ms 47308 KB Output is correct
8 Correct 25 ms 47400 KB Output is correct
9 Correct 23 ms 47400 KB Output is correct
10 Correct 508 ms 49396 KB Output is correct
11 Correct 385 ms 49360 KB Output is correct
12 Correct 45 ms 49300 KB Output is correct
13 Correct 633 ms 49484 KB Output is correct
14 Correct 634 ms 49484 KB Output is correct
15 Correct 409 ms 49396 KB Output is correct
16 Execution timed out 4046 ms 178700 KB Time limit exceeded
17 Halted 0 ms 0 KB -