oj.uz

답안 #763185

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
763185 2023-06-22T06:08:35 Z t6twotwo 늑대인간 (IOI18_werewolf) C++17
49 / 100
 4000 ms 73024 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]];
            if (qmin(min(x, y), max(x, y) + 1) >= L[i] || qmax(min(x, y), max(x, y) + 1) <= R[i]) {
                ans[i] = 1;
                continue;
            }
            int r;
            {
                int lo = min(x, y), hi = max(x, y);
                while (lo < hi) {
                    int mi = (lo + hi + 1) / 2;
                    if ((x < y && qmin(x, mi + 1) >= L[i]) || (x > y && qmax(y, mi + 1) <= R[i])) {
                        lo = mi;
                    } else {
                        hi = mi - 1;
                    }
                }
                r = lo;
            }
            int l;
            {
                int lo = min(x, y), hi = max(x, y);
                while (lo < hi) {
                    int mi = (lo + hi) / 2;
                    if ((x < y && qmax(mi, y + 1) <= R[i]) || (x > y && qmin(mi, x + 1) >= L[i])) {
                        hi = mi;
                    } else {
                        lo = mi + 1;
                    }
                }
                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
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 220 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 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 220 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 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 282 ms 724 KB Output is correct
11 Correct 204 ms 724 KB Output is correct
12 Correct 4 ms 1236 KB Output is correct
13 Correct 225 ms 724 KB Output is correct
14 Correct 142 ms 724 KB Output is correct
15 Correct 185 ms 840 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 522 ms 64524 KB Output is correct
2 Correct 293 ms 73024 KB Output is correct
3 Correct 295 ms 72820 KB Output is correct
4 Correct 323 ms 72948 KB Output is correct
5 Correct 336 ms 72948 KB Output is correct
6 Correct 487 ms 72928 KB Output is correct
7 Correct 565 ms 72936 KB Output is correct
8 Correct 283 ms 72932 KB Output is correct
9 Correct 236 ms 72896 KB Output is correct
10 Correct 228 ms 72832 KB Output is correct
11 Correct 224 ms 72816 KB Output is correct
12 Correct 258 ms 72908 KB Output is correct
13 Correct 448 ms 72928 KB Output is correct
14 Correct 454 ms 72932 KB Output is correct
15 Correct 459 ms 72808 KB Output is correct
16 Correct 478 ms 72896 KB Output is correct
17 Correct 565 ms 72816 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 220 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 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 282 ms 724 KB Output is correct
11 Correct 204 ms 724 KB Output is correct
12 Correct 4 ms 1236 KB Output is correct
13 Correct 225 ms 724 KB Output is correct
14 Correct 142 ms 724 KB Output is correct
15 Correct 185 ms 840 KB Output is correct
16 Correct 522 ms 64524 KB Output is correct
17 Correct 293 ms 73024 KB Output is correct
18 Correct 295 ms 72820 KB Output is correct
19 Correct 323 ms 72948 KB Output is correct
20 Correct 336 ms 72948 KB Output is correct
21 Correct 487 ms 72928 KB Output is correct
22 Correct 565 ms 72936 KB Output is correct
23 Correct 283 ms 72932 KB Output is correct
24 Correct 236 ms 72896 KB Output is correct
25 Correct 228 ms 72832 KB Output is correct
26 Correct 224 ms 72816 KB Output is correct
27 Correct 258 ms 72908 KB Output is correct
28 Correct 448 ms 72928 KB Output is correct
29 Correct 454 ms 72932 KB Output is correct
30 Correct 459 ms 72808 KB Output is correct
31 Correct 478 ms 72896 KB Output is correct
32 Correct 565 ms 72816 KB Output is correct
33 Execution timed out 4026 ms 30960 KB Time limit exceeded
34 Halted 0 ms 0 KB -