oj.uz

Submission #763177

# Submission time Handle Problem Language Result Execution time Memory
763177 2023-06-22T05:55:54 Z t6twotwo Werewolf (IOI18_werewolf) C++17
0 / 100
 545 ms 64520 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) {
    vector<vector<int>> adj(N);
    for (int i = 0; i < X.size(); i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    bool line = 1;
    for (int i = 0; i < N; i++) {
        if (adj[i].size() > 2) {
            line = 0;
        }
    }
    int Q = S.size();
    vector<int> ans(Q);
    if (line) {
        int x = 0;
        while (adj[x].size() == 2) {
            x++;
        }
        vector<int> a{x, adj[x][0]};
        for (int i = 0; i < N - 2; i++) {
            a.push_back(adj[a[i + 1]][0] ^ adj[a[i + 1]][1] ^ a[i]);
        }
        vector<int> pos(N);
        for (int i = 0; i < N; i++) {
            pos[a[i]] = i;
        }
        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) {
            int k = lg[r - l];
            return min(smin[l][k], smin[r - (1 << k)][k]);
        };
        auto qmax = [&](int l, int r) {
            int k = lg[r - l];
            return max(smax[l][k], smax[r - (1 << k)][k]);
        };
        for (int i = 0; i < Q; i++) {
            int x = pos[S[i]];
            int y = pos[E[i]];
            int r;
            {
                int lo = min(x, y), hi = max(x, y);
                while (lo < hi) {
                    int mi = (lo + hi) / 2;
                    if ((x < y && qmin(x, mi + 1) >= L[i]) || (x > y && qmax(y, mi + 1) <= R[i])) {
                        lo = mi + 1;
                    } else {
                        hi = mi;
                    }
                }
                r = lo;
            }
            int l;
            {
                int lo = min(x, y), hi = max(x, y);
                while (lo < hi) {
                    int mi = (lo + hi + 1) / 2;
                    if ((x < y && qmax(mi, y + 1) <= R[i]) || (x > y && qmin(mi, x + 1) >= L[i])) {
                        hi = mi - 1;
                    } else {
                        lo = mi;
                    }
                }
                l = lo;
            }
            ans[i] = l <= r;
        }
        return ans;
    }
    for (int i = 0; i < Q; i++) {
        bool vis[N][2]{};
        vis[S[i]][0] = 1;
        queue<pair<int, int>> q;
        q.emplace(S[i], 0);
        while (!q.empty()) {
            auto [x, z] = q.front();
            q.pop();
            if (z == 0 && x <= R[i] && !vis[x][1]) {
                vis[x][1] = 1;
                q.emplace(x, 1);
            }
            for (int y : adj[x]) {
                if (z == 0) {
                    if (y >= L[i] && !vis[y][0]) {
                        vis[y][0] = 1;
                        q.emplace(y, 0);
                    }
                } else {
                    if (y <= R[i] && !vis[y][1]) {
                        vis[y][1] = 1;
                        q.emplace(y, 1);
                    }
                }
            }
        }
        ans[i] = vis[E[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:6:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |     for (int i = 0; i < X.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 284 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 284 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 545 ms 64520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 284 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -