제출 #429207

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
429207	2021-06-15 18:55:40	CrouchingDragon	Werewolf (IOI18_werewolf)	C++17	100 / 100	1064 ms	87480 KiB

werewolf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
    int M = (int)size(X), Q = (int)size(S);
    vector<vector<int>> left(N), right(N);
    for (int j = 0; j < M; ++j) {
        int u = X[j], v = Y[j];
        if (u > v) swap(u, v);
        left[v].push_back(u);
        right[u].push_back(v);
    }
    vector<int> pl(N, N), pr(N, -1), p(N);
    auto find = [&](auto& self, int u, int lb, int ub) -> int {
        return p[u] < lb || ub < p[u] ? u : p[u] = self(self, p[u], lb, ub);
    };
    fill(begin(p), end(p), N);
    for (int u = 0; u < N; ++u) {
        for (auto v : left[u]) {
            v = find(find, v, 0, N - 1);
            if (v != u) p[v] = pl[v] = u;
        }
    }
    fill(begin(p), end(p), -1);
    for (int u = N - 1; u >= 0; --u) {
        for (auto v : right[u]) {
            v = find(find, v, 0, N - 1);
            if (v != u) p[v] = pr[v] = u;
        }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51