Submission #997802

#	Time	Username	Problem	Language	Result	Execution time	Memory
997802		biank	Werewolf (IOI18_werewolf)	C++14	49 / 100	4075 ms	60980 KiB

werewolf

#include <bits/stdc++.h>

using namespace std;

#define sz(x) int(x.size())
using vi = vector<int>;

const int MAX_N = 2e5 + 9;

vi adj[MAX_N];

void dfs(int u, vi &vis, int L, int R) {
    vis[u] = 1;
    for (int v : adj[u]) {
        if (!vis[v] && L <= v && v <= R) dfs(v, vis, L, R);
    }
}

vi brute(int N, vi S, vi E, vi L, vi R) {
    int Q = sz(S);
    vi ans(Q, 0);
    for (int i = 0; i < Q; i++) {
        vi human(N, 0), wolf(N, 0);
        dfs(S[i], human, L[i], N - 1);
        dfs(E[i], wolf, 0, R[i]);
        for (int j = 0; j < N; j++) {
            if (human[j] && wolf[j]) {
                ans[i] = 1;
                break;
            }
        }
    }
    return ans;
}

const int MAX_K = 20;

pair<int, int> st[MAX_K][MAX_N];
#define op(a, b) {min(a.first, b.first), max(a.second, b.second)}

pair<int, int> query(int l, int r) {
    int log = 31 - __builtin_clz(r - l);
    return op(st[log][l], st[log][r - (1 << log)]);
}

pair<int, int> range(int N, int pos, int L, int R) {
    int lo = -1, hi = pos;
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        auto [mini, maxi] = query(mid, pos + 1);
        if (L <= mini && maxi <= R) hi = mid;
        else lo = mid;
    }
    int leftPos = hi;
    lo = pos, hi = N;
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        auto [mini, maxi] = query(pos, mid + 1);
        if (L <= mini && maxi <= R) lo = mid;
        else hi = mid;
    }
    int rightPos = lo;
    return {leftPos, rightPos};
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
    int M = sz(X), Q = sz(S);
    for (int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    if (N <= 3000 && M <= 6000 && Q <= 3000) return brute(N, S, E, L, R);
    vi v, p(N);
    for (int i = 0; i < N; i++) {
        if (sz(adj[i]) == 1) {
            p[i] = sz(v);
            v.push_back(i);
            break;
        }
    }
    int par = -1;
    while (sz(v) < N) {
        for (int u : adj[v.back()]) {
            if (u != par) {
                par = v.back();
                p[u] = sz(v);
                v.push_back(u);
                break;
            }
        }
    }
    for (int i = 0; i < N; i++) {
        st[0][i] = {v[i], v[i]};
    }
    for (int i = 0; i < MAX_K - 1; i++) {
        for (int j = 0; j < N - (1 << i); j++) {
            st[i + 1][j] = op(st[i][j], st[i][j + (1 << i)]);
        }
    }
    vi ans(Q, 0);
    for (int i = 0; i < Q; i++) {
        auto [a, b] = range(N, p[S[i]], L[i], N - 1);
        auto [c, d] = range(N, p[E[i]], 0, R[i]);
        for (int t = 0; t < 2; t++) {
            if (a <= c && c <= b) ans[i] = 1;
            if (a <= d && d <= b) ans[i] = 1;
            swap(a, c), swap(b, d);
        }
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::pair<int, int> range(int, int, int, int)':
werewolf.cpp:50:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |         auto [mini, maxi] = query(mid, pos + 1);
      |              ^
werewolf.cpp:58:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |         auto [mini, maxi] = query(pos, mid + 1);
      |              ^
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:102:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |         auto [a, b] = range(N, p[S[i]], L[i], N - 1);
      |              ^
werewolf.cpp:103:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |         auto [c, d] = range(N, p[E[i]], 0, R[i]);
      |              ^

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