oj.uz

Submission #1078615

# Submission time Handle Problem Language Result Execution time Memory
1078615 2024-08-27T23:06:51 Z ProtonDecay314 Werewolf (IOI18_werewolf) C++17
100 / 100
 1371 ms 270096 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef short int si;
typedef vector<si> vsi;
typedef vector<vsi> vvsi;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

/*
I need to create
1. A regular union find with an extra augmentation:
each parent node optionally points to an internal node of a union find tree
2. A union find tree, with each node initialized with null values for smallest, largest, and time unified. It must also have 18 binary jump pointers per node
3. A merge sort tree, with each interval storing points within it

It might also help to store the [vL, vR] values per node. Could be done with a vpi tbh

Overall complexity is... O((n + q) log^2 n)
*/
const int MAX_JUMP_PTR = 18;

class UfTree {
    public:
        typedef vector<UfTree*> vutp;
        int l, r; // smallest and largest values
        UfTree *lt, *rt;
        int t; // unification time
        int orig_ind;
        vutp up;

        UfTree(int a_t, UfTree* a_lt, UfTree* a_rt, int a_orig_ind): t(a_t), lt(a_lt), rt(a_rt), orig_ind(a_orig_ind), up(MAX_JUMP_PTR, nullptr) {};

        void postorder_traverse(int low_new_ind, UfTree* par, vi& ind, vutp& leaf_ptrs) {
            up[0] = par;
            // cout << "cur_t = " << t << ", par_t = " << par->t << ", ptr is null = " << (lt == nullptr) << endl;
            if(lt == nullptr) {
                // Compute new index
                l = r = low_new_ind;

                ind[orig_ind] = l;
                leaf_ptrs[orig_ind] = this;
                return;
            }

            lt->postorder_traverse(low_new_ind, this, ind, leaf_ptrs);
            rt->postorder_traverse(lt->r + 1, this, ind, leaf_ptrs); // ! check if lt->r + 1 is right

            l = lt->l;
            r = rt->r;
        }

        void compute_jump_pointers() {
            for(int i = 1; i < MAX_JUMP_PTR; i++) {
                up[i] = up[i - 1]->up[i - 1];
            }

            if(lt == nullptr) return;

            lt->compute_jump_pointers();
            rt->compute_jump_pointers();
        }

        UfTree* find_most_recent_node(int qt) {
            UfTree* cur = this;

            int cur_jump_sz = MAX_JUMP_PTR - 1;

            while(cur_jump_sz >= 0 && cur != cur->up[0]) {
                if(cur->up[cur_jump_sz]->t > qt) {
                    // The creation time of the next node is later than the query time. Reduce jump size
                    cur_jump_sz--;
                } else {
                    cur = cur->up[cur_jump_sz];
                }
            }

            return cur;
        }
};

class Uf {
    public:
        typedef vector<UfTree*> vutp;
        int n;
        vutp uf_tree_node;
        vi par;
        vi csize;
        int ncomps;

        Uf(int a_n): n(a_n), uf_tree_node(n, nullptr), par(n, 0), csize(n, 1), ncomps(a_n) {
            for(int i = 0; i < n; i++) {
                uf_tree_node[i] = new UfTree(0, nullptr, nullptr, i);
                par[i] = i;
            }
        }

        int find(int i) {
            return (i == par[i] ? i : par[i] = find(par[i])); // ! warning, might be wrong, I don't usually implement it this way
        }

        int conn(int i, int j) {
            return find(i) == find(j);
        }

        void unify(int i, int j, int t) {
            int pari = find(i), parj = find(j);

            if(pari == parj) return;

            UfTree* new_uftree_node = new UfTree(t, uf_tree_node[parj], uf_tree_node[pari], -1);

            if(csize[pari] < csize[parj]) {
                uf_tree_node[parj] = new_uftree_node;
                par[pari] = parj;
                csize[parj] += csize[pari];
            } else {
                uf_tree_node[pari] = new_uftree_node;
                par[parj] = pari;
                csize[pari] += csize[parj];
            }

            ncomps++;
        }
};

// Merge sort tree
class Tree {
    public:
        int l, r;
        Tree *lt, *rt;
        vi y;

        Tree(int a_l, int a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), y() {};

        void combine() {
            int lp = 0;
            int rp = 0;
            int ls = lt->y.size();
            int rs = rt->y.size();

            while(lp < ls && rp < rs) {
                if(lt->y[lp] < rt->y[rp]) {
                    y.pb(lt->y[lp]);
                    lp++;
                } else {
                    y.pb(rt->y[rp]);
                    rp++;
                }
            }

            while(lp < ls) {
                y.pb(lt->y[lp]);
                lp++;
            }

            while(rp < rs) {
                y.pb(rt->y[rp]);
                rp++;
            }
        }

        void build(const vpi& a) {
            if(l == r) {
                y.pb(a[l].se);
                return;
            }

            int m = (l + r) >> 1;
            lt = new Tree(l, m);
            rt = new Tree(m + 1, r);

            lt->build(a);
            rt->build(a);
            
            combine();
        }

        bool qry(int qvll, int qvlr, int qvrl, int qvrr) {
            if(qvll > r || qvlr < l) return false;

            if(qvll == l && qvlr == r) {
                // Check if the current y includes something in the range [qvrl, qvrr]
                int li = -1, ri = y.size();

                while(ri - li > 1) {
                    int m = (li + ri) >> 1;

                    if(y[m] >= qvrl) ri = m;
                    else li = m;
                }

                if(ri == y.size()) return false;
                return y[ri] <= qvrr;
            }

            int m = (l + r) >> 1;

            return lt->qry(qvll, min(qvlr, m), qvrl, qvrr) || rt->qry(max(qvll, m + 1), qvlr, qvrl, qvrr);
        }
};

vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
    int q = s.size(), m = x.size();
    
    // Getting edge list representation
    vpi el;

    for(int i = 0; i < m; i++) {
        el.pb({x[i], y[i]});
    }

    // Stores the vL, vR values
    typedef vector<UfTree*> vutp;
    vi vl(n, -1);
    vi vr(n, -1);
    vutp vlp(n, nullptr);
    vutp vrp(n, nullptr);

    // Sort by increasing max element
    sort(el.begin(), el.end(), [](pi e1, pi e2) {return max(e1.fi, e1.se) < max(e2.fi, e2.se);});

    // Process R
    int e_ptr = 0; // Pointer to the current edge

    Uf ufr(n);

    for(int i = 0; i < n; i++) {
        while(e_ptr < m && max(el[e_ptr].fi, el[e_ptr].se) == i) {
            ufr.unify(el[e_ptr].fi, el[e_ptr].se, i);
            e_ptr++;
        }
    }

    // Sort by decreasing min element
    sort(el.begin(), el.end(), [](pi e1, pi e2) {return min(e1.fi, e1.se) > min(e2.fi, e2.se);});

    // Process L
    e_ptr = 0; // Pointer to the current edge
    Uf ufl(n);

    for(int i = 0; i < n; i++) {
        while(e_ptr < m && min(el[e_ptr].fi, el[e_ptr].se) == n - i - 1) {
            ufl.unify(el[e_ptr].fi, el[e_ptr].se, -(n - i - 1));
            e_ptr++;
        }
    }

    /*
    For both left and right union find trees:
    1. Perform reindexing
    2. Compute the l and r values per node too
    3. Finally, compute the parent jump pointer. This will be needed for the computation of all jump pointers later
    */
    UfTree* luft = ufl.uf_tree_node[ufl.find(0)];
    UfTree* ruft = ufr.uf_tree_node[ufr.find(0)];

    luft->postorder_traverse(0, luft, vl, vlp);
    ruft->postorder_traverse(0, ruft, vr, vrp);
    for(int i = 0; i < n; i++) {
        vlp[i]->t = -(n - 1);
    }


    // Compute binary jump pointers for both left and right union find trees
    // Use PREORDER (we want higher nodes to be processed before lower nodes)
    luft->compute_jump_pointers();
    ruft->compute_jump_pointers();

    // Set-up the merge sort tree. Initialize it with the [vl, vr] values, vl on the x-axis, vr on the y-axis
    vpi vlvr(n, {-1, -1});
    for(int i = 0; i < n; i++) {
        vlvr[i] = {vl[i], vr[i]};
        // cout << vl[i] << " " << vr[i] << endl;
    }

    sort(vlvr.begin(), vlvr.end());

    Tree tr(0, n - 1);
    tr.build(vlvr);

    // Query from the merge sort tree
    vi ans(q, false);
    for(int i = 0; i < q; i++) {
        UfTree* ln = vlp[s[i]]->find_most_recent_node(-l[i]);
        UfTree* rn = vrp[e[i]]->find_most_recent_node(r[i]);
        // cout << ln->l << " " << ln->r << " " << rn->l << " " << rn->r << endl;
        ans[i] = tr.qry(ln->l, ln->r, rn->l, rn->r) ? 1 : 0;
    }

    // Congrats bro, you just ACed the penultimate IOI problem :))
    return ans;
}

Compilation message

werewolf.cpp: In constructor 'UfTree::UfTree(int, UfTree*, UfTree*, int)':
werewolf.cpp:51:13: warning: 'UfTree::t' will be initialized after [-Wreorder]
   51 |         int t; // unification time
      |             ^
werewolf.cpp:50:17: warning:   'UfTree* UfTree::lt' [-Wreorder]
   50 |         UfTree *lt, *rt;
      |                 ^~
werewolf.cpp:55:9: warning:   when initialized here [-Wreorder]
   55 |         UfTree(int a_t, UfTree* a_lt, UfTree* a_rt, int a_orig_ind): t(a_t), lt(a_lt), rt(a_rt), orig_ind(a_orig_ind), up(MAX_JUMP_PTR, nullptr) {};
      |         ^~~~~~
werewolf.cpp: In member function 'bool Tree::qry(int, int, int, int)':
werewolf.cpp:216:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |                 if(ri == y.size()) return false;
      |                    ~~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 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 344 KB Output is correct
5 Correct 0 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 0 ms 348 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 600 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 344 KB Output is correct
5 Correct 0 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 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 7 ms 4184 KB Output is correct
11 Correct 7 ms 4188 KB Output is correct
12 Correct 7 ms 4188 KB Output is correct
13 Correct 7 ms 4188 KB Output is correct
14 Correct 6 ms 4192 KB Output is correct
15 Correct 8 ms 4188 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 846 ms 260800 KB Output is correct
2 Correct 841 ms 263168 KB Output is correct
3 Correct 721 ms 261736 KB Output is correct
4 Correct 702 ms 261376 KB Output is correct
5 Correct 726 ms 261312 KB Output is correct
6 Correct 774 ms 261100 KB Output is correct
7 Correct 775 ms 261232 KB Output is correct
8 Correct 756 ms 263108 KB Output is correct
9 Correct 678 ms 261832 KB Output is correct
10 Correct 569 ms 261224 KB Output is correct
11 Correct 587 ms 261572 KB Output is correct
12 Correct 561 ms 261316 KB Output is correct
13 Correct 1340 ms 263192 KB Output is correct
14 Correct 1359 ms 263184 KB Output is correct
15 Correct 1301 ms 263200 KB Output is correct
16 Correct 1324 ms 263104 KB Output is correct
17 Correct 755 ms 261228 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 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 344 KB Output is correct
5 Correct 0 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 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 7 ms 4184 KB Output is correct
11 Correct 7 ms 4188 KB Output is correct
12 Correct 7 ms 4188 KB Output is correct
13 Correct 7 ms 4188 KB Output is correct
14 Correct 6 ms 4192 KB Output is correct
15 Correct 8 ms 4188 KB Output is correct
16 Correct 846 ms 260800 KB Output is correct
17 Correct 841 ms 263168 KB Output is correct
18 Correct 721 ms 261736 KB Output is correct
19 Correct 702 ms 261376 KB Output is correct
20 Correct 726 ms 261312 KB Output is correct
21 Correct 774 ms 261100 KB Output is correct
22 Correct 775 ms 261232 KB Output is correct
23 Correct 756 ms 263108 KB Output is correct
24 Correct 678 ms 261832 KB Output is correct
25 Correct 569 ms 261224 KB Output is correct
26 Correct 587 ms 261572 KB Output is correct
27 Correct 561 ms 261316 KB Output is correct
28 Correct 1340 ms 263192 KB Output is correct
29 Correct 1359 ms 263184 KB Output is correct
30 Correct 1301 ms 263200 KB Output is correct
31 Correct 1324 ms 263104 KB Output is correct
32 Correct 755 ms 261228 KB Output is correct
33 Correct 989 ms 261632 KB Output is correct
34 Correct 247 ms 30228 KB Output is correct
35 Correct 1128 ms 263432 KB Output is correct
36 Correct 908 ms 261568 KB Output is correct
37 Correct 1054 ms 262852 KB Output is correct
38 Correct 965 ms 261908 KB Output is correct
39 Correct 949 ms 264900 KB Output is correct
40 Correct 1097 ms 270008 KB Output is correct
41 Correct 820 ms 262548 KB Output is correct
42 Correct 627 ms 261500 KB Output is correct
43 Correct 960 ms 267196 KB Output is correct
44 Correct 908 ms 262848 KB Output is correct
45 Correct 656 ms 265424 KB Output is correct
46 Correct 707 ms 265152 KB Output is correct
47 Correct 1371 ms 263316 KB Output is correct
48 Correct 1359 ms 263108 KB Output is correct
49 Correct 1368 ms 263288 KB Output is correct
50 Correct 1367 ms 263136 KB Output is correct
51 Correct 1006 ms 270096 KB Output is correct
52 Correct 997 ms 270084 KB Output is correct