oj.uz

Submission #798180

# Submission time Handle Problem Language Result Execution time Memory
798180 2023-07-30T12:54:23 Z TheSahib Werewolf (IOI18_werewolf) C++14
49 / 100
 3674 ms 144636 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 2e5 + 5;
const int BLOCK = 150;
const int LOGMAX = 17;
 
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 30 ms 80784 KB Output is correct
2 Correct 29 ms 80836 KB Output is correct
3 Correct 30 ms 80796 KB Output is correct
4 Correct 29 ms 80780 KB Output is correct
5 Correct 29 ms 80836 KB Output is correct
6 Correct 29 ms 80776 KB Output is correct
7 Correct 38 ms 80848 KB Output is correct
8 Correct 30 ms 80844 KB Output is correct
9 Correct 29 ms 80764 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 80784 KB Output is correct
2 Correct 29 ms 80836 KB Output is correct
3 Correct 30 ms 80796 KB Output is correct
4 Correct 29 ms 80780 KB Output is correct
5 Correct 29 ms 80836 KB Output is correct
6 Correct 29 ms 80776 KB Output is correct
7 Correct 38 ms 80848 KB Output is correct
8 Correct 30 ms 80844 KB Output is correct
9 Correct 29 ms 80764 KB Output is correct
10 Correct 58 ms 81788 KB Output is correct
11 Correct 58 ms 81720 KB Output is correct
12 Correct 63 ms 81720 KB Output is correct
13 Correct 61 ms 81864 KB Output is correct
14 Correct 64 ms 81740 KB Output is correct
15 Correct 63 ms 81812 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3415 ms 136888 KB Output is correct
2 Correct 3404 ms 139300 KB Output is correct
3 Correct 3374 ms 137748 KB Output is correct
4 Correct 3116 ms 137124 KB Output is correct
5 Correct 3146 ms 137084 KB Output is correct
6 Correct 3437 ms 137012 KB Output is correct
7 Correct 2905 ms 137012 KB Output is correct
8 Correct 3464 ms 139312 KB Output is correct
9 Correct 2684 ms 137744 KB Output is correct
10 Correct 2199 ms 137120 KB Output is correct
11 Correct 2266 ms 137080 KB Output is correct
12 Correct 2268 ms 137020 KB Output is correct
13 Correct 3168 ms 144272 KB Output is correct
14 Correct 3264 ms 144272 KB Output is correct
15 Correct 3159 ms 144288 KB Output is correct
16 Correct 3089 ms 144296 KB Output is correct
17 Correct 2817 ms 137012 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 80784 KB Output is correct
2 Correct 29 ms 80836 KB Output is correct
3 Correct 30 ms 80796 KB Output is correct
4 Correct 29 ms 80780 KB Output is correct
5 Correct 29 ms 80836 KB Output is correct
6 Correct 29 ms 80776 KB Output is correct
7 Correct 38 ms 80848 KB Output is correct
8 Correct 30 ms 80844 KB Output is correct
9 Correct 29 ms 80764 KB Output is correct
10 Correct 58 ms 81788 KB Output is correct
11 Correct 58 ms 81720 KB Output is correct
12 Correct 63 ms 81720 KB Output is correct
13 Correct 61 ms 81864 KB Output is correct
14 Correct 64 ms 81740 KB Output is correct
15 Correct 63 ms 81812 KB Output is correct
16 Correct 3415 ms 136888 KB Output is correct
17 Correct 3404 ms 139300 KB Output is correct
18 Correct 3374 ms 137748 KB Output is correct
19 Correct 3116 ms 137124 KB Output is correct
20 Correct 3146 ms 137084 KB Output is correct
21 Correct 3437 ms 137012 KB Output is correct
22 Correct 2905 ms 137012 KB Output is correct
23 Correct 3464 ms 139312 KB Output is correct
24 Correct 2684 ms 137744 KB Output is correct
25 Correct 2199 ms 137120 KB Output is correct
26 Correct 2266 ms 137080 KB Output is correct
27 Correct 2268 ms 137020 KB Output is correct
28 Correct 3168 ms 144272 KB Output is correct
29 Correct 3264 ms 144272 KB Output is correct
30 Correct 3159 ms 144288 KB Output is correct
31 Correct 3089 ms 144296 KB Output is correct
32 Correct 2817 ms 137012 KB Output is correct
33 Correct 3674 ms 137172 KB Output is correct
34 Correct 1974 ms 100872 KB Output is correct
35 Correct 3516 ms 139016 KB Output is correct
36 Correct 3419 ms 137444 KB Output is correct
37 Correct 3513 ms 138424 KB Output is correct
38 Correct 3436 ms 137844 KB Output is correct
39 Incorrect 3194 ms 144636 KB Output isn't correct
40 Halted 0 ms 0 KB -