oj.uz

Submission #798132

# Submission time Handle Problem Language Result Execution time Memory
798132 2023-07-30T11:40:57 Z TheSahib Werewolf (IOI18_werewolf) C++14
100 / 100
 3711 ms 180500 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX = 2e5 + 5;
const int BLOCK = 100;
const int LOGMAX = 19;

struct order{
    vector<int> v;
    bitset<MAX> st[MAX / BLOCK + 2];
    void preCalc(){
        int p = 0;
        for (int i = 0; i < v.size(); i++)
        {
            if(i % BLOCK == 0){
                p++;
                st[p] = st[p - 1];
            }
            st[p][v[i]] = 1;
        }
    }
    bitset<MAX> query(int p){
        bitset<MAX> ans = st[p / BLOCK];
        for (int i = p / BLOCK * BLOCK; i <= p; i++)
        {
            ans[v[i]] = 1;
        }
        return ans;
    }
};

int n;
struct graph{
    vector<int> tree[MAX];
    int par[LOGMAX][MAX];
    order v;
    int timeIn[MAX], timeOut[MAX];

    void dfs(int node, int p){
        par[0][node] = p;
        timeIn[node] = v.v.size();
        v.v.push_back(node);
        for(int to:tree[node]){
            if(to == p) continue;
            dfs(to, node);
        }
        timeOut[node] = v.v.size() - 1;
    }
    void preCalc(){
        for (int j = 1; j < LOGMAX; j++)
        {
            for (int i = 0; i < n; i++)
            {
                par[j][i] = par[j - 1][par[j - 1][i]];
            }
        }
        v.preCalc();
    }
    int lift1(int v, int a){
        for(int j = LOGMAX - 1; j >= 0; --j){
            int u = par[j][v];
            if(u >= a){
                v = u;
            }
        }
        return v;
    }
    int lift2(int v, int a){
        for(int j = LOGMAX - 1; j >= 0; --j){
            int u = par[j][v];
            if(u <= a){
                v = u;
            }
        }
        return v;
    }
    bitset<MAX> ask(int node){
        return v.query(timeOut[node]) ^ v.query(timeIn[node] - 1);
    }
};

vector<int> g[MAX];
graph tree1, tree2;

struct DSU{
    int par[MAX];
    bool b = 0;
    void init(int N, bool _b){
        b = _b;
        memset(par, -1, sizeof(par));
    }
    int get(int node){
        if(par[node] < 0) return node;
        return par[node] = get(par[node]);
    }
    bool unite(int v, int u){
        v = get(v);
        u = get(u);
        if(v == u) return false;
        if(v < u && b) swap(v, u);
        if(v > u && !b) swap(v, u);
        par[v] += par[u];
        par[u] = v;
        return true;
    }
};

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    n = N;
    DSU dsu;
    for (int i = 0; i < X.size(); i++)
    {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    dsu.init(N, 0);
    for (int node = N - 1; node >= 0; node--)
    {
        for(int to:g[node]){
            if(to < node) continue;
            int a = dsu.get(to);
            if(dsu.unite(node, to)){
                tree1.tree[node].push_back(a);
            }
        }
    }
    dsu.init(N, 1);
    for (int node = 0; node < N; node++)
    {
        for(int to:g[node]){
            if(to > node) continue;
            int a = dsu.get(to);
            if(dsu.unite(node, to)){
                tree2.tree[node].push_back(a);
            }
        }
    }
    tree1.dfs(0, 0);
    tree2.dfs(n - 1, n - 1);
    tree1.preCalc();
    tree2.preCalc();

    vector<int> ans(S.size());
    for (int i = 0; i < S.size(); i++)
    {
        int a = tree1.lift1(S[i], L[i]);
        int b = tree2.lift2(E[i], R[i]);
        ans[i] = (tree1.ask(a) & tree2.ask(b)).any();
    }
    return ans;
}

Compilation message

werewolf.cpp: In member function 'void order::preCalc()':
werewolf.cpp:15:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         for (int i = 0; i < v.size(); i++)
      |                         ~~^~~~~~~~~~
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:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for (int i = 0; i < X.size(); i++)
      |                     ~~^~~~~~~~~~
werewolf.cpp:146:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for (int i = 0; i < S.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 113452 KB Output is correct
2 Correct 42 ms 113492 KB Output is correct
3 Correct 39 ms 113392 KB Output is correct
4 Correct 40 ms 113432 KB Output is correct
5 Correct 40 ms 113492 KB Output is correct
6 Correct 41 ms 113428 KB Output is correct
7 Correct 39 ms 113484 KB Output is correct
8 Correct 40 ms 113480 KB Output is correct
9 Correct 41 ms 113528 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 113452 KB Output is correct
2 Correct 42 ms 113492 KB Output is correct
3 Correct 39 ms 113392 KB Output is correct
4 Correct 40 ms 113432 KB Output is correct
5 Correct 40 ms 113492 KB Output is correct
6 Correct 41 ms 113428 KB Output is correct
7 Correct 39 ms 113484 KB Output is correct
8 Correct 40 ms 113480 KB Output is correct
9 Correct 41 ms 113528 KB Output is correct
10 Correct 67 ms 114380 KB Output is correct
11 Correct 68 ms 114364 KB Output is correct
12 Correct 71 ms 114280 KB Output is correct
13 Correct 68 ms 114368 KB Output is correct
14 Correct 68 ms 114372 KB Output is correct
15 Correct 72 ms 114484 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3567 ms 172720 KB Output is correct
2 Correct 3616 ms 174940 KB Output is correct
3 Correct 3505 ms 173412 KB Output is correct
4 Correct 3276 ms 172764 KB Output is correct
5 Correct 3339 ms 172720 KB Output is correct
6 Correct 3507 ms 172660 KB Output is correct
7 Correct 2949 ms 172660 KB Output is correct
8 Correct 3526 ms 174960 KB Output is correct
9 Correct 2643 ms 173388 KB Output is correct
10 Correct 2132 ms 172768 KB Output is correct
11 Correct 2172 ms 172728 KB Output is correct
12 Correct 2379 ms 172672 KB Output is correct
13 Correct 3340 ms 179924 KB Output is correct
14 Correct 3373 ms 179920 KB Output is correct
15 Correct 3292 ms 179924 KB Output is correct
16 Correct 3275 ms 179932 KB Output is correct
17 Correct 2949 ms 172656 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 113452 KB Output is correct
2 Correct 42 ms 113492 KB Output is correct
3 Correct 39 ms 113392 KB Output is correct
4 Correct 40 ms 113432 KB Output is correct
5 Correct 40 ms 113492 KB Output is correct
6 Correct 41 ms 113428 KB Output is correct
7 Correct 39 ms 113484 KB Output is correct
8 Correct 40 ms 113480 KB Output is correct
9 Correct 41 ms 113528 KB Output is correct
10 Correct 67 ms 114380 KB Output is correct
11 Correct 68 ms 114364 KB Output is correct
12 Correct 71 ms 114280 KB Output is correct
13 Correct 68 ms 114368 KB Output is correct
14 Correct 68 ms 114372 KB Output is correct
15 Correct 72 ms 114484 KB Output is correct
16 Correct 3567 ms 172720 KB Output is correct
17 Correct 3616 ms 174940 KB Output is correct
18 Correct 3505 ms 173412 KB Output is correct
19 Correct 3276 ms 172764 KB Output is correct
20 Correct 3339 ms 172720 KB Output is correct
21 Correct 3507 ms 172660 KB Output is correct
22 Correct 2949 ms 172660 KB Output is correct
23 Correct 3526 ms 174960 KB Output is correct
24 Correct 2643 ms 173388 KB Output is correct
25 Correct 2132 ms 172768 KB Output is correct
26 Correct 2172 ms 172728 KB Output is correct
27 Correct 2379 ms 172672 KB Output is correct
28 Correct 3340 ms 179924 KB Output is correct
29 Correct 3373 ms 179920 KB Output is correct
30 Correct 3292 ms 179924 KB Output is correct
31 Correct 3275 ms 179932 KB Output is correct
32 Correct 2949 ms 172656 KB Output is correct
33 Correct 3668 ms 172812 KB Output is correct
34 Correct 1940 ms 133424 KB Output is correct
35 Correct 3711 ms 174664 KB Output is correct
36 Correct 3691 ms 173084 KB Output is correct
37 Correct 3710 ms 174072 KB Output is correct
38 Correct 3581 ms 173488 KB Output is correct
39 Correct 3380 ms 180284 KB Output is correct
40 Correct 2772 ms 179740 KB Output is correct
41 Correct 2793 ms 173712 KB Output is correct
42 Correct 2033 ms 173100 KB Output is correct
43 Correct 3393 ms 177984 KB Output is correct
44 Correct 3475 ms 174132 KB Output is correct
45 Correct 2553 ms 180500 KB Output is correct
46 Correct 2743 ms 180284 KB Output is correct
47 Correct 3293 ms 180004 KB Output is correct
48 Correct 3268 ms 179920 KB Output is correct
49 Correct 3337 ms 180008 KB Output is correct
50 Correct 3301 ms 179928 KB Output is correct
51 Correct 2334 ms 179548 KB Output is correct
52 Correct 2277 ms 179544 KB Output is correct