Submission #429205

#	Time	Username	Problem	Language	Result	Execution time	Memory
429205		CrouchingDragon	Werewolf (IOI18_werewolf)	C++17	Compilation error	0 ms	0 KiB

werewolf

#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;
        }
    }
    vector<vector<int>> F(N);
    for (int u = 0; u < N; ++u) {
        int v = pr[u];
        if (v != -1) F[v].push_back(u);
    }
    vector<int> l(N), r(N);
    int timer = 0;
    auto tour = [&](auto& self, int u) -> void {
        l[u] = timer;
        for (auto v : F[u]) self(self, v);
        r[u] = timer++;
    };
    for (int u = 0; u < N; ++u) {
        if (pr[u] == -1) tour(tour, u);
    }
    vector<int> subleft(Q), subright(Q), I(Q);
    iota(begin(I), end(I), 0);
    p = pl;
    sort(begin(I), end(I), [&](int q1, int q2){ return R[q1] < R[q2]; });
    for (auto q : I) subleft[q] = find(find, E[q], 0, R[q]);
    p = pr;
    sort(begin(I), end(I), [&](int q1, int q2){ return L[q1] > L[q2]; });
    for (auto q : I) subright[q] = find(find, S[q], L[q], N - 1);
    vector<vector<int>> queries(N);
    for (auto q : I) {
        int u = subleft[q], v = subright[q];
        if (L[q] <= v && u <= R[q]) queries[u].push_back(q);
    }
    vector<set<int>> T(N);
    vector<int> ans(Q);
    for (int u = 0; u < N; ++u) {
        T[u].insert(r[u]);
        for (auto q : queries[u]) {
            int v = subright[q];
            auto iter = T[u].lower_bound(l[v]);
            if (iter != end(T[u]) && *iter <= r[v]) ans[q] = 1;
        }
        if (int v = pl[u]; v < N) {
            if (size(T[v]) < size(T[u])) swap(T[v], T[u]);
            T[v].merge(T[u]);
        }
    }
    return ans;
}
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int N = read_int();
  int M = read_int();
  int Q = read_int();
  std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
  for (int j = 0; j < M; ++j) {
    X[j] = read_int();
    Y[j] = read_int();
  }
  for (int i = 0; i < Q; ++i) {
    S[i] = read_int();
    E[i] = read_int();
    L[i] = read_int();
    R[i] = read_int();
  }

  std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
  for (size_t i = 0; i < A.size(); ++i) {
    printf("%d\n", A[i]);
  }
  return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccsLv2l4.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc4jf9V7.o:werewolf.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status