oj.uz

Submission #980341

# Submission time Handle Problem Language Result Execution time Memory
980341 2024-05-12T05:24:56 Z Ghetto Werewolf (IOI18_werewolf) C++17
100 / 100
 1456 ms 238264 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25692 KB Output is correct
2 Correct 6 ms 25836 KB Output is correct
3 Correct 5 ms 25688 KB Output is correct
4 Correct 5 ms 25692 KB Output is correct
5 Correct 5 ms 25692 KB Output is correct
6 Correct 5 ms 25692 KB Output is correct
7 Correct 5 ms 25692 KB Output is correct
8 Correct 5 ms 25828 KB Output is correct
9 Correct 5 ms 25692 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25692 KB Output is correct
2 Correct 6 ms 25836 KB Output is correct
3 Correct 5 ms 25688 KB Output is correct
4 Correct 5 ms 25692 KB Output is correct
5 Correct 5 ms 25692 KB Output is correct
6 Correct 5 ms 25692 KB Output is correct
7 Correct 5 ms 25692 KB Output is correct
8 Correct 5 ms 25828 KB Output is correct
9 Correct 5 ms 25692 KB Output is correct
10 Correct 10 ms 27832 KB Output is correct
11 Correct 13 ms 27640 KB Output is correct
12 Correct 10 ms 27740 KB Output is correct
13 Correct 11 ms 27996 KB Output is correct
14 Correct 10 ms 27996 KB Output is correct
15 Correct 11 ms 27740 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 722 ms 212128 KB Output is correct
2 Correct 1022 ms 226268 KB Output is correct
3 Correct 856 ms 222468 KB Output is correct
4 Correct 682 ms 220748 KB Output is correct
5 Correct 672 ms 220832 KB Output is correct
6 Correct 742 ms 220776 KB Output is correct
7 Correct 593 ms 220644 KB Output is correct
8 Correct 977 ms 226544 KB Output is correct
9 Correct 708 ms 222512 KB Output is correct
10 Correct 473 ms 220800 KB Output is correct
11 Correct 499 ms 220816 KB Output is correct
12 Correct 545 ms 220656 KB Output is correct
13 Correct 901 ms 232820 KB Output is correct
14 Correct 900 ms 232472 KB Output is correct
15 Correct 936 ms 232612 KB Output is correct
16 Correct 916 ms 232620 KB Output is correct
17 Correct 599 ms 220456 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25692 KB Output is correct
2 Correct 6 ms 25836 KB Output is correct
3 Correct 5 ms 25688 KB Output is correct
4 Correct 5 ms 25692 KB Output is correct
5 Correct 5 ms 25692 KB Output is correct
6 Correct 5 ms 25692 KB Output is correct
7 Correct 5 ms 25692 KB Output is correct
8 Correct 5 ms 25828 KB Output is correct
9 Correct 5 ms 25692 KB Output is correct
10 Correct 10 ms 27832 KB Output is correct
11 Correct 13 ms 27640 KB Output is correct
12 Correct 10 ms 27740 KB Output is correct
13 Correct 11 ms 27996 KB Output is correct
14 Correct 10 ms 27996 KB Output is correct
15 Correct 11 ms 27740 KB Output is correct
16 Correct 722 ms 212128 KB Output is correct
17 Correct 1022 ms 226268 KB Output is correct
18 Correct 856 ms 222468 KB Output is correct
19 Correct 682 ms 220748 KB Output is correct
20 Correct 672 ms 220832 KB Output is correct
21 Correct 742 ms 220776 KB Output is correct
22 Correct 593 ms 220644 KB Output is correct
23 Correct 977 ms 226544 KB Output is correct
24 Correct 708 ms 222512 KB Output is correct
25 Correct 473 ms 220800 KB Output is correct
26 Correct 499 ms 220816 KB Output is correct
27 Correct 545 ms 220656 KB Output is correct
28 Correct 901 ms 232820 KB Output is correct
29 Correct 900 ms 232472 KB Output is correct
30 Correct 936 ms 232612 KB Output is correct
31 Correct 916 ms 232620 KB Output is correct
32 Correct 599 ms 220456 KB Output is correct
33 Correct 1036 ms 221840 KB Output is correct
34 Correct 210 ms 57428 KB Output is correct
35 Correct 1368 ms 225888 KB Output is correct
36 Correct 952 ms 221784 KB Output is correct
37 Correct 1321 ms 224452 KB Output is correct
38 Correct 1106 ms 222564 KB Output is correct
39 Correct 1065 ms 237680 KB Output is correct
40 Correct 834 ms 232944 KB Output is correct
41 Correct 937 ms 223620 KB Output is correct
42 Correct 564 ms 221776 KB Output is correct
43 Correct 1456 ms 231852 KB Output is correct
44 Correct 1205 ms 224440 KB Output is correct
45 Correct 800 ms 238264 KB Output is correct
46 Correct 1002 ms 237544 KB Output is correct
47 Correct 896 ms 232860 KB Output is correct
48 Correct 917 ms 232652 KB Output is correct
49 Correct 934 ms 232576 KB Output is correct
50 Correct 889 ms 232608 KB Output is correct
51 Correct 782 ms 232792 KB Output is correct
52 Correct 726 ms 232632 KB Output is correct