oj.uz

Submission #729639

# Submission time Handle Problem Language Result Execution time Memory
729639 2023-04-24T10:09:50 Z t6twotwo Werewolf (IOI18_werewolf) C++17
49 / 100
 746 ms 73068 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    int M = X.size();
    int Q = S.size();
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    if (N <= 3000 && M <= 6000 && Q <= 3000) {
        vector<int> p(N);
        function<int(int)> find = [&](int x) {
            return x == p[x] ? x : p[x] = find(p[x]);
        };
        vector<vector<int>> s(N);
        auto unite = [&](int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) {
                return;
            }
            if (s[x].size() > s[y].size()) {
                swap(x, y);
            }
            for (int z : s[x]) {
                p[z] = y;
                s[y].push_back(z);
            }
        };
        for (int i = 0; i < N; i++) {
            p[i] = i;
            s[i] = {i};
        }
        vector hi(N, vector<int>(N, -1));
        for (int x = N - 1; x >= 0; x--) {
            hi[x][x] = x;
            for (int y : adj[x]) {
                if (y < x || find(x) == find(y)) {
                    continue;
                }
                for (int u : s[find(x)]) {
                    for (int v : s[find(y)]) {
                        hi[u][v] = x;
                        hi[v][u] = x;
                    }
                }
                unite(x, y);
            }
        }
        for (int i = 0; i < N; i++) {
            p[i] = i;
            s[i] = {i};
        }
        vector lo(N, vector<int>(N, -1));
        for (int x = 0; x < N; x++) {
            lo[x][x] = x;
            for (int y : adj[x]) {
                if (y > x || find(x) == find(y)) {
                    continue;
                }
                for (int u : s[find(x)]) {
                    for (int v : s[find(y)]) {
                        lo[u][v] = x;
                        lo[v][u] = x;
                    }
                }
                unite(x, y);
            }
        }
        vector<int> ans(Q);
        for (int i = 0; i < Q; i++) {
            for (int j = L[i]; j <= R[i]; j++) {
                if (hi[S[i]][j] >= L[i] && lo[j][E[i]] <= R[i]) {
                    ans[i] = 1;
                }
            }
        }
        return ans;
    } else {
        vector<int> A;
        for (int i = 0; i < N; i++) {
            if (adj[i].size() == 1) {
                A.push_back(i);
                A.push_back(adj[i][0]);
                break;
            }
        }
        while (A.size() < N) {
            int x = A[A.size() - 2];
            int y = A[A.size() - 1];
            A.push_back(adj[y][0] ^ adj[y][1] ^ x);
        }
        vector<int> lg(N + 1);
        for (int i = 2; i <= N; i++) {
            lg[i] = lg[i / 2] + 1;
        }
        vector smin(N, vector<int>(lg[N] + 1));
        vector smax(N, vector<int>(lg[N] + 1));
        for (int i = 0; i < N; i++) {
            smin[i][0] = A[i];
            smax[i][0] = A[i];
        }
        for (int j = 0; j < lg[N]; j++) {
            for (int i = 0; i + (2 << j) <= N; i++) {
                smin[i][j + 1] = min(smin[i][j], smin[i + (1 << j)][j]);
                smax[i][j + 1] = max(smax[i][j], smax[i + (1 << j)][j]);
            }
        }
        auto qmin = [&](int l, int r) {
            if (l == r) {
                return N;
            }
            int k = lg[r - l];
            return min(smin[l][k], smin[r - (1 << k)][k]);
        };
        auto qmax = [&](int l, int r) {
            if (l == r) {
                return -1;
            }
            int k = lg[r - l];
            return max(smax[l][k], smax[r - (1 << k)][k]);
        };
        vector<int> B(N);
        for (int i = 0; i < N; i++) {
            B[A[i]] = i;
        }
        vector<int> ans(Q);
        for (int i = 0; i < Q; i++) {
            if (S[i] < L[i] || E[i] > R[i]) {
                continue;
            }
            int x = B[S[i]], u = -1;
            int y = B[E[i]], v = -1;
            if (x < y) {
                int lo = x, hi = y;
                while (lo < hi) {
                    int mi = (lo + hi + 1) / 2;
                    if (qmin(x, mi + 1) >= L[i]) {
                        lo = mi;
                    } else {
                        hi = mi - 1;
                    }
                }
                u = lo;
                lo = x, hi = y;
                while (lo < hi) {
                    int mi = (lo + hi) / 2;
                    if (qmax(mi, y + 1) <= R[i]) {
                        hi = mi;
                    } else {
                        lo = mi + 1;
                    }
                }
                v = lo;
            } else {
                int lo = y, hi = x;
                while (lo < hi) {
                    int mi = (lo + hi + 1) / 2;
                    if (qmax(y, mi + 1) <= R[i]) {
                        lo = mi;
                    } else {
                        hi = mi - 1;
                    }
                }
                u = lo;
                lo = y, hi = x;
                while (lo < hi) {
                    int mi = (lo + hi) / 2;
                    if (qmin(mi, x + 1) >= L[i]) {
                        hi = mi;
                    } else {
                        lo = mi + 1;
                    }
                }
                v = lo;
            }
            if (v <= u) {
                ans[i] = 1;
            }
        }
        return ans;
    }
}

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:90:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |         while (A.size() < N) {
      |                ~~~~~~~~~^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 179 ms 71500 KB Output is correct
11 Correct 172 ms 71500 KB Output is correct
12 Correct 155 ms 71704 KB Output is correct
13 Correct 147 ms 71452 KB Output is correct
14 Correct 128 ms 71496 KB Output is correct
15 Correct 180 ms 71704 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 64520 KB Output is correct
2 Correct 603 ms 64576 KB Output is correct
3 Correct 577 ms 72812 KB Output is correct
4 Correct 617 ms 72936 KB Output is correct
5 Correct 641 ms 73012 KB Output is correct
6 Correct 657 ms 72940 KB Output is correct
7 Correct 746 ms 72932 KB Output is correct
8 Correct 591 ms 72928 KB Output is correct
9 Correct 374 ms 72848 KB Output is correct
10 Correct 337 ms 73068 KB Output is correct
11 Correct 363 ms 72820 KB Output is correct
12 Correct 368 ms 72828 KB Output is correct
13 Correct 712 ms 72904 KB Output is correct
14 Correct 718 ms 72988 KB Output is correct
15 Correct 673 ms 72928 KB Output is correct
16 Correct 701 ms 72932 KB Output is correct
17 Correct 668 ms 72928 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 179 ms 71500 KB Output is correct
11 Correct 172 ms 71500 KB Output is correct
12 Correct 155 ms 71704 KB Output is correct
13 Correct 147 ms 71452 KB Output is correct
14 Correct 128 ms 71496 KB Output is correct
15 Correct 180 ms 71704 KB Output is correct
16 Correct 527 ms 64520 KB Output is correct
17 Correct 603 ms 64576 KB Output is correct
18 Correct 577 ms 72812 KB Output is correct
19 Correct 617 ms 72936 KB Output is correct
20 Correct 641 ms 73012 KB Output is correct
21 Correct 657 ms 72940 KB Output is correct
22 Correct 746 ms 72932 KB Output is correct
23 Correct 591 ms 72928 KB Output is correct
24 Correct 374 ms 72848 KB Output is correct
25 Correct 337 ms 73068 KB Output is correct
26 Correct 363 ms 72820 KB Output is correct
27 Correct 368 ms 72828 KB Output is correct
28 Correct 712 ms 72904 KB Output is correct
29 Correct 718 ms 72988 KB Output is correct
30 Correct 673 ms 72928 KB Output is correct
31 Correct 701 ms 72932 KB Output is correct
32 Correct 668 ms 72928 KB Output is correct
33 Runtime error 177 ms 50512 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -