Submission #991435

#	Time	Username	Problem	Language	Result	Execution time	Memory
991435		Forested	Werewolf (IOI18_werewolf)	C++17	100 / 100	2191 ms	47396 KiB

werewolf

#include <bits/stdc++.h>
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n)-1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r)-1; i >= (i32)(l); --i)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32)(x).size()
#define ALL(x) begin(x), end(x)
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

#include "werewolf.h"

class UF {
    V<i32> par;
    V<pair<i32, i32>> mnx;
public:
    UF(i32 n) : par(n, -1), mnx(n) {
        REP(i, n) {
            mnx[i] = pair<i32, i32>(i, i);
        }
    }
    i32 root(i32 x) {
        if (par[x] < 0) {
            return x;
        } else {
            return par[x] = root(par[x]);
        }
    }
    pair<i32, i32> get_minmax(i32 v) {
        i32 r = root(v);
        return mnx[r];
    }
    bool unite(i32 x, i32 y) {
        x = root(x);
        y = root(y);
        if (x == y) {
            return false;
        }
        if (-par[x] > -par[y]) {
            swap(x, y);
        }
        chmin(mnx[y].first, mnx[x].first);
        chmax(mnx[y].second, mnx[x].second);
        par[y] += par[x];
        par[x] = y;
        return true;
    }
};

V<i32> check_validity(i32 n, V<i32> x, V<i32> y, V<i32> s, V<i32> e, V<i32> l, V<i32> r) {
    i32 q = LEN(s);
    V<V<i32>> g(n);
    REP(i, LEN(x)) {
        g[x[i]].push_back(y[i]);
        g[y[i]].push_back(x[i]);
    }
    V<i32> par0(n, -1), par1(n, -1);
    {
        V<V<i32>> process(n);
        REP(i, q) {
            process[l[i]].push_back(i);
        }
        UF uf(n);
        PER(i, n) {
            for (i32 j : g[i]) {
                if (j > i) {
                    i32 tmp = uf.get_minmax(j).first;
                    if (uf.unite(i, j)) {
                        par0[tmp] = i;
                    }
                }
            }
            for (i32 j : process[i]) {
                s[j] = uf.get_minmax(s[j]).first;
            }
        }
    }
    {
        V<V<i32>> process(n);
        REP(i, q) {
            process[r[i]].push_back(i);
        }
        UF uf(n);
        REP(i, n) {
            for (i32 j : g[i]) {
                if (j < i) {
                    i32 tmp = uf.get_minmax(j).second;
                    if (uf.unite(i, j)) {
                        par1[tmp] = i;
                    }
                }
            }
            for (i32 j : process[i]) {
                e[j] = uf.get_minmax(e[j]).second;
            }
        }
    }
    V<i32> ans(q, 0);
    constexpr i32 B = 64;
    using u64 = unsigned long long;
    i32 blk = (q + B + 1) / B;
    V<u64> dp0(n, 0), dp1(n, 0);
    REP(iter, blk) {
        i32 l = B * iter;
        i32 r = min(q, l + B);
        REP(i, n) {
            dp0[i] = dp1[i] = 0;
        }
        REP(i, l, r) {
            dp0[s[i]] ^= 1ull << (i - l);
            dp1[e[i]] ^= 1ull << (i - l);
        }
        REP(i, 1, n) {
            dp0[i] |= dp0[par0[i]];
        }
        PER(i, n - 1) {
            dp1[i] |= dp1[par1[i]];
        }
        u64 t = 0;
        REP(i, n) {
            t |= dp0[i] & dp1[i];
        }
        REP(i, l, r) {
            if (t & (1ull << (i - l))) {
                ans[i] = 1;
            }
        }
    }
    return ans;
}

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