Submission #546365

#	Time	Username	Problem	Language	Result	Execution time	Memory
546365		hoanghq2004	Werewolf (IOI18_werewolf)	C++14	100 / 100	807 ms	175140 KiB

werewolf

#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "werewolf.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 4e5 + 10;

vector <int> g[N];
int a[N];

struct DSU {
    int n, ord[N];
    int in[N], out[N];
    int root[N];
    vector <int> e[N];
    DSU(int _n) {
        n = _n;
        for (int i = 0; i < n; ++i) root[i] = i;
    }
    int Find(int u) {
        return (u == root[u] ? u : root[u] = Find(root[u]));
    }
    void Union(int u, int v) {
        if ((u = Find(u)) == (v = Find(v))) return;
        e[n].push_back(u);
        e[n].push_back(v);
        root[u] = n, root[v] = n;
        root[n] = n;
        ++n;
    }
    int ti = 0;
    void dfs(int u) {
        if (e[u].size()) {
            in[u] = 1e9, out[u] = - 1e9;
            for (auto v: e[u]) dfs(v), in[u] = min(in[u], in[v]), out[u] = max(out[u], out[v]);
        } else {
            ord[ti] = u;
            in[u] = out[u] = ti;
            ++ti;
        }
    }
    void run() {
        dfs(n - 1);
    }
};

int node[N][2];
vector <pair <int, int> > QL[N], QR[N];

vector <int> st[N * 4];

void build(int id, int L, int R) {
    if (L == R) {
        st[id].push_back(a[L]);
        return;
    }
    int mid = L + R >> 1;
    build(id * 2, L, mid);
    build(id * 2 + 1, mid + 1, R);
    st[id].resize(R - L + 1);
    merge(st[id * 2].begin(), st[id * 2].end(), st[id * 2 + 1].begin(), st[id * 2 + 1].end(), st[id].begin());
}

int get(int id, int L, int R, int u, int v, int x, int y) {
    if (u > R || L > v) return 0;
    if (u <= L && R <= v) {
        auto iter = lower_bound(st[id].begin(), st[id].end(), x);
        if (iter != st[id].end() && *iter <= y) return 1;
        return 0;
    }
    int mid = L + R >> 1;
    return get(id * 2, L, mid, u, v, x, y) || get(id * 2 + 1, mid + 1, R, u, v, x, y);
}

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();
    for (int i = 0; i < m; ++i) {
        int u = X[i], v = Y[i];
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> A(q);
    for (int i = 0; i < q; ++i) {
        int u = S[i], v = E[i], l = L[i], r = R[i];
        QR[l].push_back({u, i});
        QL[r].push_back({v, i});
    }
    DSU D1(n), D2(n);
    for (int u = 0; u < n; ++u) {
        for (auto v: g[u]) {
            if (u > v) D1.Union(u, v);
        }
        for (auto [x, i]: QL[u]) node[i][0] = D1.Find(x);
    }
    for (int u = n - 1; u >= 0; --u) {
        for (auto v: g[u]) {
            if (u < v) D2.Union(u, v);
        }
        for (auto [x, i]: QR[u]) node[i][1] = D2.Find(x);
    }
    D1.run();
    D2.run();
    for (int i = 0; i < n; ++i) a[i] = D2.in[D1.ord[i]];
    build(1, 0, n - 1);
    for (int i = 0; i < q; ++i) {
        A[i] = get(1, 0, n - 1, D1.in[node[i][0]], D1.out[node[i][0]], D2.in[node[i][1]], D2.out[node[i][1]]);
    }
    return A;
}
//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)

werewolf.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
werewolf.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     int mid = L + R >> 1;
      |               ~~^~~
werewolf.cpp: In function 'int get(int, int, int, int, int, int, int)':
werewolf.cpp:79:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |     int mid = L + R >> 1;
      |               ~~^~~
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:102:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |         for (auto [x, i]: QL[u]) node[i][0] = D1.Find(x);
      |                   ^
werewolf.cpp:108:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |         for (auto [x, i]: QR[u]) node[i][1] = D2.Find(x);
      |                   ^

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