제출 #1022676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022676		efishel	늑대인간 (IOI18_werewolf)	C++17	100 / 100	2165 ms	401984 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;
    // vector <vii> qs;
    // vll vans;
    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) {
        // cerr << "at-1\n";
        u = find(u);
        v = find(v);
        if (u == v) return;
        // cerr << "at0\n";
        ll id = newId();
        // cerr << "at1\n";
        adj[id].push_back(u);
        adj[id].push_back(v);
        // cerr << "at2\n";
        bioPar[id] = id;
        // cerr << "at3\n";
        bioPar[u] = par[u] = id;
        bioPar[v] = par[v] = id;
        // cerr << "at4\n";
        nn[id] = a(nn[u], nn[v]);
        // cerr << id << " par of " << u << ' ' << v << '\n';
        // cerr << "at5\n";
        // if (qs[u].size() > qs[v].size()) swap(u, v);
        // for (auto [vth, qid] : qs[u]) {
        //     if (find(vth) == v) {
        //         vans[qid] = id;
        //     } else qs[v].push_back({ vth, qid });
        // }
    }

    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;
        // if (a(nn[bioPar[u]], x) == x) return findRoot(bioPar[u], 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++;
        // cerr << nn[u] << ' ';
        assert(adj[u].empty() == (u < n));
        if (adj[u].empty()) sub.push_back(u);
        anc[u] = { bioPar[u] };
        for (ll v : adj[u]) {
            dfs(v, sub);
            // cerr << nn[u] << ' ';
        }
        tout[u] = timer-1;
    }

    // void addQ (ll u, ll v, ll qid) {
    //     assert(qid == vans.size());
    //     qs[u].push_back({ v, qid });
    //     qs[v].push_back({ u, qid });
    //     vans.push_back(-15);
    // }
};

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

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

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

    // void update (ll id, ll val) {
    //     tree[id] = 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 (ll i = ql; i <= qr; i++)
    //         ans |= l <= tree[i] && tree[i] <= r;
    //     return ans;
    // }

    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++) {
        // adj[us[i]].push_back(vs[i]);
        // adj[vs[i]].push_back(us[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) {
        // cerr << u << ' ' << v << ' ' << w << '\n';
        // cerr << "joining\n";
        dsuMn.join(u, v);
        // cerr << "joiningee\n";
    }
    DSU dsuMx(n, [&](ll a, ll b) { return max(a, b); });
    for (auto [u, v, w] : egsMx) {
        // cerr << u << ' ' << v << ' ' << w << '\n';
        // cerr << "joining\n";
        dsuMx.join(u, v);
        // cerr << "joiningee\n";
    }
    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();
    // cerr <<  << '\n';
    vi ans(Q, -15);
    for (ll qid = 0; qid < Q; qid++) {
        assert(vl[qid] <= s[qid]);
        assert(e[qid] <= vr[qid]);
        assert(vl[qid] <= vr[qid]);
        assert(e[qid] != s[qid]);
        // ll ancMn = dsuMn.findRoot(s[qid], vl[qid]);
        // ll ancMx = dsuMx.findRoot(e[qid], vr[qid]);
        // vll accMn = dsuMn.doDfs(s[qid], vl[qid]);
        // vll accMx = dsuMx.doDfs(e[qid], vr[qid]);
        auto [lMn, rMn] = dsuMn.getRange(s[qid], vl[qid]);
        auto [lMx, rMx] = dsuMx.getRange(e[qid], vr[qid]);
        // cerr << lMn << ' ' << rMn << '\n';
        // cerr << lMx << ' ' << rMx << '\n';
        // sort(accMn.begin(), accMn.end());
        ans[qid] = st.query(lMx, rMx, lMn, rMn);
        // for (ll i : accMx) {
            // ans[qid] |= binary_search(accMn.begin(), accMn.end(), i);
        // }
        // for (ll i : accMn) cerr << i << ' '; cerr << '\n';
        // for (ll i : accMx) cerr << i << ' '; cerr << '\n';
    }
    // cerr << "ANS DONE\n";
    return ans;
}

컴파일 시 표준 에러 (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:41:5: warning:   when initialized here [-Wreorder]
   41 |     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:26:27: warning: 'DSU::a' will be initialized after [-Wreorder]
   26 |     function <ll(ll, ll)> a;
      |                           ^
werewolf.cpp:21:8: warning:   'll DSU::n' [-Wreorder]
   21 |     ll n;
      |        ^
werewolf.cpp:41:5: warning:   when initialized here [-Wreorder]
   41 |     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:98: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]
   98 |             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:99: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]
   99 |                 assert(anc[u].size() == bit);
      |                        ~~~~~~~~~~~~~~^~~~~~
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:169: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]
  169 |     for (ll i = 0; i < us.size(); i++) {
      |                    ~~^~~~~~~~~~~

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