oj.uz

Submission #798942

# Submission time Handle Problem Language Result Execution time Memory
798942 2023-07-31T07:52:27 Z TheSahib Werewolf (IOI18_werewolf) C++14
100 / 100
 3785 ms 157012 KB 
#pragma GCC target("popcnt")
#include "werewolf.h"
#include <bits/stdc++.h>

 
using namespace std;
 
const int MAX = 2e5 + 5;
const int BLOCK = 150;
const int LOGMAX = 18;
 
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:17:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         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:115:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int i = 0; i < X.size(); i++)
      |                     ~~^~~~~~~~~~
werewolf.cpp:148:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for (int i = 0; i < S.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 80844 KB Output is correct
2 Correct 29 ms 80752 KB Output is correct
3 Correct 31 ms 80788 KB Output is correct
4 Correct 32 ms 80716 KB Output is correct
5 Correct 30 ms 80768 KB Output is correct
6 Correct 30 ms 80784 KB Output is correct
7 Correct 29 ms 80852 KB Output is correct
8 Correct 29 ms 80828 KB Output is correct
9 Correct 32 ms 80808 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 80844 KB Output is correct
2 Correct 29 ms 80752 KB Output is correct
3 Correct 31 ms 80788 KB Output is correct
4 Correct 32 ms 80716 KB Output is correct
5 Correct 30 ms 80768 KB Output is correct
6 Correct 30 ms 80784 KB Output is correct
7 Correct 29 ms 80852 KB Output is correct
8 Correct 29 ms 80828 KB Output is correct
9 Correct 32 ms 80808 KB Output is correct
10 Correct 62 ms 81816 KB Output is correct
11 Correct 59 ms 81816 KB Output is correct
12 Correct 61 ms 81816 KB Output is correct
13 Correct 60 ms 81868 KB Output is correct
14 Correct 56 ms 81888 KB Output is correct
15 Correct 65 ms 81928 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3493 ms 146848 KB Output is correct
2 Correct 3573 ms 149144 KB Output is correct
3 Correct 3476 ms 147576 KB Output is correct
4 Correct 3210 ms 146908 KB Output is correct
5 Correct 3307 ms 146912 KB Output is correct
6 Correct 3564 ms 146852 KB Output is correct
7 Correct 3040 ms 146844 KB Output is correct
8 Correct 3457 ms 149088 KB Output is correct
9 Correct 2593 ms 147588 KB Output is correct
10 Correct 2177 ms 146948 KB Output is correct
11 Correct 2196 ms 146900 KB Output is correct
12 Correct 2315 ms 146872 KB Output is correct
13 Correct 3333 ms 154116 KB Output is correct
14 Correct 3293 ms 154112 KB Output is correct
15 Correct 3301 ms 154120 KB Output is correct
16 Correct 3249 ms 154124 KB Output is correct
17 Correct 2886 ms 146844 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 80844 KB Output is correct
2 Correct 29 ms 80752 KB Output is correct
3 Correct 31 ms 80788 KB Output is correct
4 Correct 32 ms 80716 KB Output is correct
5 Correct 30 ms 80768 KB Output is correct
6 Correct 30 ms 80784 KB Output is correct
7 Correct 29 ms 80852 KB Output is correct
8 Correct 29 ms 80828 KB Output is correct
9 Correct 32 ms 80808 KB Output is correct
10 Correct 62 ms 81816 KB Output is correct
11 Correct 59 ms 81816 KB Output is correct
12 Correct 61 ms 81816 KB Output is correct
13 Correct 60 ms 81868 KB Output is correct
14 Correct 56 ms 81888 KB Output is correct
15 Correct 65 ms 81928 KB Output is correct
16 Correct 3493 ms 146848 KB Output is correct
17 Correct 3573 ms 149144 KB Output is correct
18 Correct 3476 ms 147576 KB Output is correct
19 Correct 3210 ms 146908 KB Output is correct
20 Correct 3307 ms 146912 KB Output is correct
21 Correct 3564 ms 146852 KB Output is correct
22 Correct 3040 ms 146844 KB Output is correct
23 Correct 3457 ms 149088 KB Output is correct
24 Correct 2593 ms 147588 KB Output is correct
25 Correct 2177 ms 146948 KB Output is correct
26 Correct 2196 ms 146900 KB Output is correct
27 Correct 2315 ms 146872 KB Output is correct
28 Correct 3333 ms 154116 KB Output is correct
29 Correct 3293 ms 154112 KB Output is correct
30 Correct 3301 ms 154120 KB Output is correct
31 Correct 3249 ms 154124 KB Output is correct
32 Correct 2886 ms 146844 KB Output is correct
33 Correct 3783 ms 147016 KB Output is correct
34 Correct 1978 ms 112328 KB Output is correct
35 Correct 3785 ms 149164 KB Output is correct
36 Correct 3694 ms 147356 KB Output is correct
37 Correct 3636 ms 148424 KB Output is correct
38 Correct 3568 ms 147836 KB Output is correct
39 Correct 3429 ms 154508 KB Output is correct
40 Correct 2864 ms 157012 KB Output is correct
41 Correct 2959 ms 147948 KB Output is correct
42 Correct 2074 ms 147376 KB Output is correct
43 Correct 3616 ms 153864 KB Output is correct
44 Correct 3678 ms 148368 KB Output is correct
45 Correct 2735 ms 154860 KB Output is correct
46 Correct 2834 ms 154500 KB Output is correct
47 Correct 3472 ms 154272 KB Output is correct
48 Correct 3498 ms 154120 KB Output is correct
49 Correct 3515 ms 154260 KB Output is correct
50 Correct 3572 ms 154128 KB Output is correct
51 Correct 2577 ms 156872 KB Output is correct
52 Correct 2473 ms 156864 KB Output is correct