Submission #555812

#	Time	Username	Problem	Language	Result	Execution time	Memory
555812		cheissmart	Werewolf (IOI18_werewolf)	C++14	100 / 100	1108 ms	196160 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e6 + 7;

int p1[N], jump1[N], time1[N], l1[N], r1[N];
vi T1[N];
int st1[N][20];
int find1(int u) {
    return jump1[u] == u ? u : jump1[u] = find1(jump1[u]);
}

int p2[N], jump2[N], time2[N], l2[N], r2[N];
vi T2[N];
int st2[N][20];
int find2(int u) {
    return jump2[u] == u ? u : jump2[u] = find2(jump2[u]);
}

int bit[N];
void add(int pos, int val) {
    pos++;
    for(; pos < N; pos += pos & -pos)
        bit[pos] += val;
}
int qry(int pos) {
    pos++;
    int res = 0;
    for(; pos; pos -= pos & -pos)
        res += bit[pos];
    return res;
}


vi check_validity(int n, vi a, vi b, vi S, vi E, vi L, vi R) {
    int m = SZ(a), q = SZ(S);
    V<vi> G(n);
    for(int i = 0; i < m; i++) {
        G[a[i]].PB(b[i]);
        G[b[i]].PB(a[i]);
    }
    int rt1, rt2;
    {
        int cnt = n;
        for(int i = 0; i < n; i++) {
            time1[i] = jump1[i] = p1[i] = i;
            for(int j:G[i]) if(j < i) {
                int x = find1(j), y = find1(i);
                if(x == y) continue;
                jump1[x] = jump1[y] = p1[x] = p1[y] = cnt;
                T1[cnt].PB(x), T1[cnt].PB(y);
                p1[cnt] = jump1[cnt] = cnt;
                time1[cnt] = i;
                cnt++;
            }
        }
        rt1 = cnt - 1;
        for(int i = 0; i < cnt; i++)
            st1[i][0] = p1[i];
        for(int j = 1; j < 20; j++)
            for(int i = 0; i < cnt; i++)
                st1[i][j] = st1[st1[i][j - 1]][j - 1];
    }
    {
        int cnt = n;
        for(int i = n - 1; i >= 0; i--) {
            time2[i] = jump2[i] = p2[i] = i;
            for(int j:G[i]) if(j > i) {
                int x = find2(j), y = find2(i);
                if(x == y) continue;
                jump2[x] = jump2[y] = p2[x] = p2[y] = cnt;
                T2[cnt].PB(x), T2[cnt].PB(y);
                p2[cnt] = jump2[cnt] = cnt;
                time2[cnt] = i;
                cnt++;
            }
        }
        rt2 = cnt - 1;
        for(int i = 0; i < cnt; i++)
            st2[i][0] = p2[i];
        for(int j = 1; j < 20; j++)
            for(int i = 0; i < cnt; i++)
                st2[i][j] = st2[st2[i][j - 1]][j - 1];
    }

    vi order1;
    {
        function<void(int)> dfs = [&] (int u) {
            l1[u] = SZ(order1);
            if(T1[u].empty()) {
                assert(0 <= u && u < n);
                order1.PB(u);
            }
            for(int v:T1[u])
                dfs(v);
            r1[u] = SZ(order1);
        };
        dfs(rt1);
    }
    vi pos(n);
    for(int i = 0; i < n; i++)
        pos[order1[i]] = i;

    vi order2;
    {
        function<void(int)> dfs = [&] (int u) {
            l2[u] = SZ(order2);
            if(T2[u].empty()) {
                assert(0 <= u && u < n);
                order2.PB(pos[u]);
            }
            for(int v:T2[u])
                dfs(v);
            r2[u] = SZ(order2);
        };
        dfs(rt2);
    }
    vi ans(q);
    V<V<array<int, 3>>> ev(n);
    for(int i = 0; i < q; i++) {
        int e = E[i], s = S[i], l = L[i], r = R[i];
        for(int j = 19; j >= 0; j--) {
            if(time1[st1[e][j]] <= r) {
                e = st1[e][j];
            }
        }
        for(int j = 19; j >= 0; j--) {
            if(time2[st2[s][j]] >= l) {
                s = st2[s][j];
            }
        }
        int lb = l1[e], rb = r1[e];
        if(l2[s]) ev[l2[s] - 1].PB({i, rb, lb});
        ev[r2[s] - 1].PB({i, lb, rb});
    }
    for(int i = 0; i < n; i++) {
        add(order2[i], 1);
        for(auto[qid, l, r]:ev[i]) {
            if(l < r) {
                ans[qid] += qry(r - 1) - qry(l - 1);
            } else {
                swap(l, r);
                ans[qid] -= qry(r - 1) - qry(l - 1);
            }
        }
    }
    for(int i = 0; i < q; i++)
        ans[i] = ans[i] > 0;
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:153:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |         for(auto[qid, l, r]:ev[i]) {
      |                 ^

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