oj.uz

답안 #1022673

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1022673 2024-07-13T22:20:25 Z efishel 늑대인간 (IOI18_werewolf) C++17
15 / 100
 4000 ms 142020 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 += 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);
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 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 11 ms 2396 KB Output is correct
11 Correct 8 ms 2396 KB Output is correct
12 Correct 5 ms 2396 KB Output is correct
13 Correct 13 ms 2396 KB Output is correct
14 Correct 16 ms 2396 KB Output is correct
15 Correct 12 ms 2528 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 600 ms 138696 KB Output is correct
2 Execution timed out 4058 ms 142020 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 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 11 ms 2396 KB Output is correct
11 Correct 8 ms 2396 KB Output is correct
12 Correct 5 ms 2396 KB Output is correct
13 Correct 13 ms 2396 KB Output is correct
14 Correct 16 ms 2396 KB Output is correct
15 Correct 12 ms 2528 KB Output is correct
16 Correct 600 ms 138696 KB Output is correct
17 Execution timed out 4058 ms 142020 KB Time limit exceeded
18 Halted 0 ms 0 KB -