Submission #980341

#	Time	Username	Problem	Language	Result	Execution time	Memory
980341		Ghetto	Werewolf (IOI18_werewolf)	C++17	100 / 100	1456 ms	238264 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 2e5 + 5;

int n;
vector<int> adj[MAX_N];

int par[2][MAX_N];
vector<int> children[2][MAX_N];
int find_par(int ind, int u) {
    if (par[ind][u] == u) return u;
    par[ind][u] = find_par(ind, par[ind][u]);
    return par[ind][u];
}
void merge(int ind, int u, int v) {
    u = find_par(ind, u), v = find_par(ind, v);
    if (u == v) return;
    par[ind][v] = u, children[ind][u].push_back(v);
}
void precomp1(int ind) {
    for (int u = 0; u < n; u++) par[ind][u] = u;
    
    vector<int> nodes;
    for (int u = 0; u < n; u++) nodes.push_back(u);
    if (ind == 0) reverse(nodes.begin(), nodes.end());

    for (int u : nodes) {
        for (int v : adj[u]) {
            if (ind == 0 && v < u) continue;
            if (ind == 1 && v > u) continue;
            merge(ind, u, v);
        }
    }

    // if (ind == 1) {
    //     for (int u = 0; u < n; u++) {
    //         cout << u << ": ";
    //         for (int v : children[ind][u]) cout << v << " ";
    //         cout << endl;
    //     }
    // }
}

int n_ids[2], id[2][MAX_N], rev_id[2][MAX_N], f_id[2][MAX_N];
int anc[2][MAX_N][22];
void dfs(int ind, int u) {
    n_ids[ind]++, id[ind][u] = n_ids[ind], rev_id[ind][n_ids[ind]] = u;
    for (int v : children[ind][u]) dfs(ind, v), anc[ind][v][0] = u;
    f_id[ind][u] = n_ids[ind];
}
int bin_lift(int ind, int u, int x) { // Should never be a problem that weight for < n uninited
    for (int i = 19; i >= 0; i--) {
        if (anc[ind][u][i] == -1) continue;
        if (ind == 0 && anc[ind][u][i] < x) continue;
        if (ind == 1 && anc[ind][u][i] > x) continue;
        u = anc[ind][u][i];
    }
    return u;
}
void precomp2(int ind) {
    for (int i = 0; i <= 19; i++)
        for (int u = 0; u < n; u++)
            anc[ind][u][i] = -1;

    int top = (ind == 0) ? 0 : n - 1;
    dfs(ind, top);

    for (int i = 1; i <= 19; i++) {
        for (int u = 0; u < n; u++) {
            if (anc[ind][u][i - 1] == -1) anc[ind][u][i] = -1;
            else anc[ind][u][i] = anc[ind][anc[ind][u][i - 1]][i - 1];
        }
    }
        
    // if (ind == 0 || ind == 1) {
    //     for (int u = 0; u < n; u++) {
    //         cout << u << ": " << id[ind][u] << endl;
    //     }
    // }
}

struct Node {
    int val;
    Node* l_child, * r_child;
    Node(int x) {
        val = x, l_child = r_child = nullptr;
    }
    Node(Node* l, Node* r) {
        val = l->val + r->val, l_child = l, r_child = r;
    }
};
Node* root[MAX_N];
Node* build(int lo = 1, int hi = n) {
    if (lo == hi) return new Node(0);
    int mid = (lo + hi) / 2;
    return new Node(build(lo, mid), build(mid + 1, hi));
}
Node* update(int i, Node* u, int lo = 1, int hi = n) {
    if (i < lo || i > hi) return nullptr;
    if (lo == hi) return new Node(1);
    int mid = (lo + hi) / 2;
    Node* l_resp = update(i, u->l_child, lo, mid), * r_resp = update(i, u->r_child, mid + 1, hi);
    return new Node((l_resp) ? l_resp : u->l_child, (r_resp) ? r_resp : u->r_child);
}
int query(int l, int r, Node* u, int lo = 1, int hi = n) {
    if (l > hi || r < lo) return 0;
    if (l <= lo && hi <= r) return u->val;
    int mid = (lo + hi) / 2;
    return query(l, r, u->l_child, lo, mid) + query(l, r, u->r_child, mid + 1, hi);
}
int query2d(int l, int r, int lo, int hi) {
    return query(lo, hi, root[r]) - query(lo, hi, root[l - 1]);
}
void precomp3() {
    root[0] = build();
    for (int i = 1; i <= n_ids[0]; i++) root[i] = update(id[1][rev_id[0][i]], root[i - 1]);
    // for (int i = 1; i <= n_ids[0]; i++) cout << rev_id[0][i] << " ";
    // cout << endl;
    // for (int i = 1; i <= n_ids[1]; i++) cout << rev_id[1][i] << " ";
    // cout << endl;
}

vector<int> check_validity(int tmp_n, vector<int> edge1, vector<int> edge2, vector<int> s, vector<int> f, vector<int> l, vector<int> r) {
    n = tmp_n;
    for (int i = 0; i < edge1.size(); i++)
        adj[edge1[i]].push_back(edge2[i]), adj[edge2[i]].push_back(edge1[i]);
    
    for (int i = 0; i <= 1; i++) precomp1(i);
    for (int i = 0; i <= 1; i++) precomp2(i);
    precomp3();
    
    vector<int> ans;
    for (int tc = 0; tc < s.size(); tc++) {
        int u = bin_lift(0, s[tc], l[tc]), v = bin_lift(1, f[tc], r[tc]);
        // cout << u << " " << v << endl;
        bool new_ans = query2d(id[0][u], f_id[0][u], id[1][v], f_id[1][v]);
        ans.push_back(new_ans);
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:127:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for (int i = 0; i < edge1.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
werewolf.cpp:135:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int tc = 0; tc < s.size(); tc++) {
      |                      ~~~^~~~~~~~~~

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