Submission #625204

#	Time	Username	Problem	Language	Result	Execution time	Memory
625204		yuto1115	Werewolf (IOI18_werewolf)	C++17	100 / 100	700 ms	64572 KiB

werewolf

#include "werewolf.h"
#include "bits/stdc++.h"
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vp = vector<P>;
using vvp = vector<vp>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    } else {
        return false;
    }
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    } else {
        return false;
    }
}

class unionfind {
    int n;
    vi p;
public:
    unionfind(int n) : n(n), p(n, -1) {}
    
    int root(int x) {
        if (p[x] < 0) return x;
        return p[x] = root(p[x]);
    }
    
    bool same(int x, int y) { return root(x) == root(y); }
    
    bool merge(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return false;
        if (p[x] > p[y]) swap(x, y);
        p[x] += p[y];
        p[y] = x;
        return true;
    }
};

class BIT {
    int n;
    vi d;
    
    int sum(int p) {
        ++p;
        int res = 0;
        for (; p >= 1; p -= p & -p) {
            res += d[p];
        }
        return res;
    }

public:
    BIT(int n) : n(n), d(n + 1) {}
    
    void add(int p, int x = 1) {
        assert(0 <= p and p < n);
        ++p;
        for (; p <= n; p += p & -p) {
            d[p] += x;
        }
    }
    
    int sum(int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        return sum(r - 1) - sum(l - 1);
    }
};

vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
    int m = SZ(x), q = SZ(s);
    vvi ord(2, vi(n));
    vvi ql(2, vi(q));
    vvi qr(2, vi(q));
    rep(i, 2) {
        vp es;
        rep(j, m) {
            if (x[j] > y[j]) swap(x[j], y[j]);
            if (!i) es.eb(x[j], y[j]);
            else es.eb(y[j], x[j]);
        }
        if (!i) sort(rall(es));
        else sort(all(es));
        unionfind uf(n);
        vi rt(n);
        iota(all(rt), 0);
        vvi G(n);
        for (auto[u, v]: es) {
            if (uf.same(u, v)) continue;
            v = rt[uf.root(v)];
            G[u].pb(v);
            G[v].pb(u);
            uf.merge(u, v);
            rt[uf.root(u)] = u;
        }
        vvi par(20, vi(n, -1));
        vi in(n), out(n);
        int iter = 0;
        auto dfs = [&](auto &dfs, int u, int p) -> void {
            par[0][u] = p;
            ord[i][u] = in[u] = iter++;
            for (int v: G[u]) {
                if (v == p) continue;
                dfs(dfs, v, u);
            }
            out[u] = iter;
        };
        dfs(dfs, (!i ? 0 : n - 1), -1);
        rep(k, 19) rep(j, n) {
                if (par[k][j] == -1) continue;
                par[k + 1][j] = par[k][par[k][j]];
            }
        rep(j, q) {
            int now = (!i ? s[j] : e[j]);
            rrep(k, 20) {
                if (par[k][now] == -1) continue;
                if (!i and par[k][now] < l[j]) continue;
                if (i and par[k][now] > r[j]) continue;
                now = par[k][now];
            }
//            cerr << now << endl;
            ql[i][j] = in[now];
            qr[i][j] = out[now];
        }
//        rep(j, n) cerr << j << ' ' << in[j] << ' ' << out[j] << endl;
//        rep(k, 20) rep(j, n) cerr << par[k][j] << (j == n - 1 ? '\n' : ' ');
    }
    vector<vector<tuple<int, int, int>>> qs(n + 1);
    rep(i, q) {
        int xl = ql[0][i];
        int xr = qr[0][i];
        int yl = ql[1][i];
        int yr = qr[1][i];
//        cerr << xl << ' ' << xr << ' ' << yl << ' ' << yr << endl;
        qs[xl].eb(yl, yr, -(i + 1));
        qs[xr].eb(yl, yr, i);
    }
    vi ans(q);
    vp pt;
    rep(i, n) pt.eb(ord[0][i], ord[1][i]);
    sort(all(pt));
    BIT bt(n);
    for (auto[i, j]: pt) {
        bt.add(j);
        for (auto[yl, yr, t]: qs[i + 1]) {
            if (t < 0) ans[-(t + 1)] -= bt.sum(yl, yr);
            else ans[t] += bt.sum(yl, yr);
        }
    }
    rep(i, q) chmin(ans[i], 1);
    return ans;
}

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