oj.uz

Submission #1022663

# Submission time Handle Problem Language Result Execution time Memory
1022663 2024-07-13T21:48:34 Z efishel Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 90576 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 451 ms 1884 KB Output is correct
11 Correct 335 ms 1624 KB Output is correct
12 Correct 21 ms 1624 KB Output is correct
13 Correct 360 ms 1884 KB Output is correct
14 Correct 141 ms 1892 KB Output is correct
15 Correct 320 ms 2024 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4067 ms 90576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 451 ms 1884 KB Output is correct
11 Correct 335 ms 1624 KB Output is correct
12 Correct 21 ms 1624 KB Output is correct
13 Correct 360 ms 1884 KB Output is correct
14 Correct 141 ms 1892 KB Output is correct
15 Correct 320 ms 2024 KB Output is correct
16 Execution timed out 4067 ms 90576 KB Time limit exceeded
17 Halted 0 ms 0 KB -