oj.uz

Submission #1022672

# Submission time Handle Problem Language Result Execution time Memory
1022672 2024-07-13T22:19:31 Z efishel Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 105348 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;
    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);
        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), /* 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;
    }

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

    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);
        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 > 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);
    dsuMx.dfs(dsuMx.par.size()-1, ordMx);
    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;
}

Compilation message

werewolf.cpp: In constructor 'DSU::DSU(ll, std::function<long long int(long long int, long long int)>)':
werewolf.cpp:25:27: warning: 'DSU::a' will be initialized after [-Wreorder]
   25 |     function <ll(ll, ll)> a;
      |                           ^
werewolf.cpp:20:8: warning:   'll DSU::n' [-Wreorder]
   20 |     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), /* 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:151: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]
  151 |     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 0 ms 348 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 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 0 ms 348 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 13 ms 2052 KB Output is correct
11 Correct 8 ms 1884 KB Output is correct
12 Correct 3 ms 1884 KB Output is correct
13 Correct 16 ms 1884 KB Output is correct
14 Correct 16 ms 1884 KB Output is correct
15 Correct 13 ms 2016 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 102344 KB Output is correct
2 Execution timed out 4058 ms 105348 KB Time limit exceeded
3 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 0 ms 348 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 13 ms 2052 KB Output is correct
11 Correct 8 ms 1884 KB Output is correct
12 Correct 3 ms 1884 KB Output is correct
13 Correct 16 ms 1884 KB Output is correct
14 Correct 16 ms 1884 KB Output is correct
15 Correct 13 ms 2016 KB Output is correct
16 Correct 377 ms 102344 KB Output is correct
17 Execution timed out 4058 ms 105348 KB Time limit exceeded
18 Halted 0 ms 0 KB -