Submission #1022663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022663		efishel	늑대인간 (IOI18_werewolf)	C++17	15 / 100	4067 ms	90576 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;
    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);
        return id;
    }

    DSU (ll n, function <ll(ll, ll)> a): par(n), sz(n, 1), nn(n), bioPar(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) {
        if (bioPar[u] == u) 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;
    }

    void dfs (ll u, vll &sub) {
        // cerr << nn[u] << ' ';
        assert(adj[u].empty() == (u < n));
        if (adj[u].empty()) sub.push_back(u);
        for (ll v : adj[u]) {
            dfs(v, sub);
            // cerr << nn[u] << ' ';
        }
    }

    // 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);
    // }
};

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 eee;
    dsuMn.dfs(dsuMn.par.size()-1, eee);
    // 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]);
        sort(accMn.begin(), accMn.end());
        ans[qid] = 0;
        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;
}

Compilation message (stderr)

werewolf.cpp: In constructor 'DSU::DSU(ll, std::function<long long int(long long int, long long int)>)':
werewolf.cpp:23:27: warning: 'DSU::a' will be initialized after [-Wreorder]
   23 |     function <ll(ll, ll)> a;
      |                           ^
werewolf.cpp:18:8: warning:   'll DSU::n' [-Wreorder]
   18 |     ll n;
      |        ^
werewolf.cpp:35:5: warning:   when initialized here [-Wreorder]
   35 |     DSU (ll n, function <ll(ll, ll)> a): par(n), sz(n, 1), nn(n), bioPar(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 function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:100: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]
  100 |     for (ll i = 0; i < us.size(); i++) {
      |                    ~~^~~~~~~~~~~

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