Submission #1022679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022679		efishel	Werewolf (IOI18_werewolf)	C++17	100 / 100	2395 ms	398328 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 2E5+16;

struct Edge {
    ll u, v, w;
};

struct DSU {
    vll par, sz, nn, bioPar;
    vector <vll> anc;
    vll tin, tout;
    ll timer;
    ll n;
    vii funnyEgs;
    vector <vll> adj;
    function <ll(ll, ll)> a;

    ll newId () {
        ll id = par.size();
        par.push_back(id);
        bioPar.push_back(id);
        sz.push_back(1);
        adj.push_back(vll({}));
        nn.push_back(-15);
        tin.push_back(-15);
        tout.push_back(-15);
        anc.push_back(vll({}));
        return id;
    }

    DSU (ll n, function <ll(ll, ll)> a): par(n), sz(n, 1), nn(n), bioPar(n), tin(n, -15), tout(n, -15), timer(0), anc(n), /* qs(n, vii({})), */ funnyEgs(0), adj(n, vll({})), a(a), n(n) { iota(par.begin(), par.end(), 0); iota(nn.begin(), nn.end(), 0); }

    ll find (ll u) { return u == par[u] ? u : par[u] = find(par[u]); }

    void join (ll u, ll v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        ll id = newId();
        adj[id].push_back(u);
        adj[id].push_back(v);
        bioPar[id] = id;
        bioPar[u] = par[u] = id;
        bioPar[v] = par[v] = id;
        nn[id] = a(nn[u], nn[v]);
    }

    ll findRoot (ll u, ll x) {
        for (ll bit = 17; bit >= 0; bit--) {
            if (a(nn[anc[u][bit]], x) != x) continue;
            u = anc[u][bit];
        }
        assert(a(nn[u], x) == x);
        if (u != anc[u][0]) assert(a(nn[anc[u][0]], x) != x);
        return u;
    }

    vll doDfs (ll u, ll x) {
        ll ahm = findRoot(u, x);
        vll ans;
        dfs(ahm, ans);
        return ans;
    }

    ii getRange (ll u, ll x) {
        ll ahm = findRoot(u, x);
        return { tin[ahm], tout[ahm] };
    }

    void buildBinLift () {
        for (ll bit = 1; bit < 18; bit++) {
            for (ll u = 0; u < anc.size(); u++) {
                assert(anc[u].size() == bit);
                anc[u].push_back(anc[anc[u][bit-1]][bit-1]);
            }
        }
    }

    void dfs (ll u, vll &sub) {
        tin[u] = timer;
        if (u < n) timer++;
        anc[u] = { bioPar[u] };
        for (ll v : adj[u])
            dfs(v, sub);
        tout[u] = timer-1;
    }
};

struct SegTree {
    vector <vll> tree;
    ll n;

    SegTree (ll n): tree(2*n, vll({})), n(n) {}

    void update (ll id, ll val) {
        for (id += n; id > 0; id >>= 1)
            tree[id].push_back(val);
    }

    void build () {
        for (ll id = 0; id < 2*n; id++)
            sort(tree[id].begin(), tree[id].end());
    }

    bool query (ll ql, ll qr, ll l, ll r) {
        bool ans = false;
        for (ql += n, qr += n+1; ql < qr; ql >>= 1, qr >>= 1) {
            if (ql&1) { ans |= upper_bound(tree[ql].begin(), tree[ql].end(), r) - lower_bound(tree[ql].begin(), tree[ql].end(), l); ql++; }
            if (qr&1) { --qr; ans |= upper_bound(tree[qr].begin(), tree[qr].end(), r) - lower_bound(tree[qr].begin(), tree[qr].end(), l); }
        }
        return ans;
    }
};

vi check_validity (int n, vi us, vi vs, vi s, vi e, vi vl, vi vr) {
    ll Q = s.size();
    vector <Edge> egsMn, egsMx;
    for (ll i = 0; i < us.size(); i++) {
        egsMn.push_back({ us[i], vs[i], min(us[i], vs[i]) });
        egsMx.push_back({ us[i], vs[i], max(us[i], vs[i]) });
    }
    sort(egsMn.begin(), egsMn.end(), [&](Edge a, Edge b) { return a.w > b.w; });
    sort(egsMx.begin(), egsMx.end(), [&](Edge a, Edge b) { return a.w < b.w; });
    DSU dsuMn(n, [&](ll a, ll b) { return min(a, b); });
    for (auto [u, v, w] : egsMn) dsuMn.join(u, v);
    DSU dsuMx(n, [&](ll a, ll b) { return max(a, b); });
    for (auto [u, v, w] : egsMx) dsuMx.join(u, v);
    vll ordMn, ordMx;
    dsuMn.dfs(dsuMn.par.size()-1, ordMn);
    dsuMn.buildBinLift();
    dsuMx.dfs(dsuMx.par.size()-1, ordMx);
    dsuMx.buildBinLift();
    SegTree st(n);
    for (ll u = 0; u < n; u++)
        st.update(dsuMx.tin[u], dsuMn.tin[u]);
    st.build();
    vi ans(Q, -15);
    for (ll qid = 0; qid < Q; qid++) {
        auto [lMn, rMn] = dsuMn.getRange(s[qid], vl[qid]);
        auto [lMx, rMx] = dsuMx.getRange(e[qid], vr[qid]);
        ans[qid] = st.query(lMx, rMx, lMn, rMn);
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In constructor 'DSU::DSU(ll, std::function<long long int(long long int, long long int)>)':
werewolf.cpp:20:8: warning: 'DSU::timer' will be initialized after [-Wreorder]
   20 |     ll timer;
      |        ^~~~~
werewolf.cpp:18:18: warning:   'std::vector<std::vector<long long int> > DSU::anc' [-Wreorder]
   18 |     vector <vll> anc;
      |                  ^~~
werewolf.cpp:39:5: warning:   when initialized here [-Wreorder]
   39 |     DSU (ll n, function <ll(ll, ll)> a): par(n), sz(n, 1), nn(n), bioPar(n), tin(n, -15), tout(n, -15), timer(0), anc(n), /* qs(n, vii({})), */ funnyEgs(0), adj(n, vll({})), a(a), n(n) { iota(par.begin(), par.end(), 0); iota(nn.begin(), nn.end(), 0); }
      |     ^~~
werewolf.cpp:24:27: warning: 'DSU::a' will be initialized after [-Wreorder]
   24 |     function <ll(ll, ll)> a;
      |                           ^
werewolf.cpp:21:8: warning:   'll DSU::n' [-Wreorder]
   21 |     ll n;
      |        ^
werewolf.cpp:39:5: warning:   when initialized here [-Wreorder]
   39 |     DSU (ll n, function <ll(ll, ll)> a): par(n), sz(n, 1), nn(n), bioPar(n), tin(n, -15), tout(n, -15), timer(0), anc(n), /* qs(n, vii({})), */ funnyEgs(0), adj(n, vll({})), a(a), n(n) { iota(par.begin(), par.end(), 0); iota(nn.begin(), nn.end(), 0); }
      |     ^~~
werewolf.cpp: In member function 'void DSU::buildBinLift()':
werewolf.cpp:80:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             for (ll u = 0; u < anc.size(); u++) {
      |                            ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from werewolf.cpp:2:
werewolf.cpp:81:38: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   81 |                 assert(anc[u].size() == bit);
      |                        ~~~~~~~~~~~~~~^~~~~~
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:126:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for (ll i = 0; i < us.size(); i++) {
      |                    ~~^~~~~~~~~~~

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