oj.uz

Submission #798082

# Submission time Handle Problem Language Result Execution time Memory
798082 2023-07-30T10:59:02 Z TheSahib Werewolf (IOI18_werewolf) C++14
15 / 100
 1413 ms 524288 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

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

int n;
struct graph{
    vector<int> tree[MAX];
    int par[LOGMAX][MAX];
    bitset<5000> st[MAX];
    void dfs(int node, int p){
        par[0][node] = p;
        for(int to:tree[node]){
            if(to == p) continue;
            dfs(to, node);
            st[node] |= st[to];
        }
        st[node][node] = 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]];
            }
        }
    }
    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;
    }
};

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.st[a] & tree2.st[b]).any();
    }
    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:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 0; i < X.size(); i++)
      |                     ~~^~~~~~~~~~
werewolf.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for (int i = 0; i < S.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 262728 KB Output is correct
2 Correct 99 ms 262736 KB Output is correct
3 Correct 89 ms 262732 KB Output is correct
4 Correct 92 ms 262628 KB Output is correct
5 Correct 102 ms 262748 KB Output is correct
6 Correct 90 ms 262744 KB Output is correct
7 Correct 101 ms 262636 KB Output is correct
8 Correct 90 ms 262752 KB Output is correct
9 Correct 90 ms 262660 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 262728 KB Output is correct
2 Correct 99 ms 262736 KB Output is correct
3 Correct 89 ms 262732 KB Output is correct
4 Correct 92 ms 262628 KB Output is correct
5 Correct 102 ms 262748 KB Output is correct
6 Correct 90 ms 262744 KB Output is correct
7 Correct 101 ms 262636 KB Output is correct
8 Correct 90 ms 262752 KB Output is correct
9 Correct 90 ms 262660 KB Output is correct
10 Correct 101 ms 263592 KB Output is correct
11 Correct 87 ms 263500 KB Output is correct
12 Correct 93 ms 263480 KB Output is correct
13 Correct 93 ms 263608 KB Output is correct
14 Correct 103 ms 263684 KB Output is correct
15 Correct 100 ms 263556 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 1413 ms 524288 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 262728 KB Output is correct
2 Correct 99 ms 262736 KB Output is correct
3 Correct 89 ms 262732 KB Output is correct
4 Correct 92 ms 262628 KB Output is correct
5 Correct 102 ms 262748 KB Output is correct
6 Correct 90 ms 262744 KB Output is correct
7 Correct 101 ms 262636 KB Output is correct
8 Correct 90 ms 262752 KB Output is correct
9 Correct 90 ms 262660 KB Output is correct
10 Correct 101 ms 263592 KB Output is correct
11 Correct 87 ms 263500 KB Output is correct
12 Correct 93 ms 263480 KB Output is correct
13 Correct 93 ms 263608 KB Output is correct
14 Correct 103 ms 263684 KB Output is correct
15 Correct 100 ms 263556 KB Output is correct
16 Runtime error 1413 ms 524288 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -