oj.uz

Submission #798135

# Submission time Handle Problem Language Result Execution time Memory
798135 2023-07-30T11:44:24 Z TheSahib Werewolf (IOI18_werewolf) C++14
100 / 100
 3902 ms 407320 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX = 2e5 + 5;
const int BLOCK = 30;
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: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 119 ms 341836 KB Output is correct
2 Correct 113 ms 341892 KB Output is correct
3 Correct 108 ms 341780 KB Output is correct
4 Correct 108 ms 341708 KB Output is correct
5 Correct 109 ms 341824 KB Output is correct
6 Correct 125 ms 341744 KB Output is correct
7 Correct 111 ms 341832 KB Output is correct
8 Correct 109 ms 341760 KB Output is correct
9 Correct 108 ms 341812 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 341836 KB Output is correct
2 Correct 113 ms 341892 KB Output is correct
3 Correct 108 ms 341780 KB Output is correct
4 Correct 108 ms 341708 KB Output is correct
5 Correct 109 ms 341824 KB Output is correct
6 Correct 125 ms 341744 KB Output is correct
7 Correct 111 ms 341832 KB Output is correct
8 Correct 109 ms 341760 KB Output is correct
9 Correct 108 ms 341812 KB Output is correct
10 Correct 142 ms 342652 KB Output is correct
11 Correct 141 ms 342692 KB Output is correct
12 Correct 140 ms 342712 KB Output is correct
13 Correct 136 ms 342772 KB Output is correct
14 Correct 138 ms 342772 KB Output is correct
15 Correct 141 ms 342736 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3856 ms 399332 KB Output is correct
2 Correct 3902 ms 401796 KB Output is correct
3 Correct 3684 ms 400180 KB Output is correct
4 Correct 3384 ms 399544 KB Output is correct
5 Correct 3388 ms 399516 KB Output is correct
6 Correct 3742 ms 399520 KB Output is correct
7 Correct 2958 ms 399440 KB Output is correct
8 Correct 3730 ms 401740 KB Output is correct
9 Correct 2899 ms 400156 KB Output is correct
10 Correct 2234 ms 399552 KB Output is correct
11 Correct 2301 ms 399508 KB Output is correct
12 Correct 2408 ms 399548 KB Output is correct
13 Correct 3368 ms 406708 KB Output is correct
14 Correct 3335 ms 406768 KB Output is correct
15 Correct 3429 ms 406708 KB Output is correct
16 Correct 3390 ms 406720 KB Output is correct
17 Correct 3001 ms 399472 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 341836 KB Output is correct
2 Correct 113 ms 341892 KB Output is correct
3 Correct 108 ms 341780 KB Output is correct
4 Correct 108 ms 341708 KB Output is correct
5 Correct 109 ms 341824 KB Output is correct
6 Correct 125 ms 341744 KB Output is correct
7 Correct 111 ms 341832 KB Output is correct
8 Correct 109 ms 341760 KB Output is correct
9 Correct 108 ms 341812 KB Output is correct
10 Correct 142 ms 342652 KB Output is correct
11 Correct 141 ms 342692 KB Output is correct
12 Correct 140 ms 342712 KB Output is correct
13 Correct 136 ms 342772 KB Output is correct
14 Correct 138 ms 342772 KB Output is correct
15 Correct 141 ms 342736 KB Output is correct
16 Correct 3856 ms 399332 KB Output is correct
17 Correct 3902 ms 401796 KB Output is correct
18 Correct 3684 ms 400180 KB Output is correct
19 Correct 3384 ms 399544 KB Output is correct
20 Correct 3388 ms 399516 KB Output is correct
21 Correct 3742 ms 399520 KB Output is correct
22 Correct 2958 ms 399440 KB Output is correct
23 Correct 3730 ms 401740 KB Output is correct
24 Correct 2899 ms 400156 KB Output is correct
25 Correct 2234 ms 399552 KB Output is correct
26 Correct 2301 ms 399508 KB Output is correct
27 Correct 2408 ms 399548 KB Output is correct
28 Correct 3368 ms 406708 KB Output is correct
29 Correct 3335 ms 406768 KB Output is correct
30 Correct 3429 ms 406708 KB Output is correct
31 Correct 3390 ms 406720 KB Output is correct
32 Correct 3001 ms 399472 KB Output is correct
33 Correct 3818 ms 399480 KB Output is correct
34 Correct 2104 ms 361748 KB Output is correct
35 Correct 3740 ms 401444 KB Output is correct
36 Correct 3780 ms 399872 KB Output is correct
37 Correct 3803 ms 400900 KB Output is correct
38 Correct 3715 ms 400268 KB Output is correct
39 Correct 3431 ms 407056 KB Output is correct
40 Correct 2801 ms 406496 KB Output is correct
41 Correct 2935 ms 400464 KB Output is correct
42 Correct 2090 ms 399992 KB Output is correct
43 Correct 3582 ms 404896 KB Output is correct
44 Correct 3778 ms 400848 KB Output is correct
45 Correct 2652 ms 407320 KB Output is correct
46 Correct 2829 ms 407136 KB Output is correct
47 Correct 3297 ms 406792 KB Output is correct
48 Correct 3326 ms 406708 KB Output is correct
49 Correct 3351 ms 406796 KB Output is correct
50 Correct 3388 ms 406712 KB Output is correct
51 Correct 2395 ms 406404 KB Output is correct
52 Correct 2353 ms 406336 KB Output is correct