oj.uz

Submission #583093

# Submission time Handle Problem Language Result Execution time Memory
583093 2022-06-24T20:18:39 Z definitelynotmee Werewolf (IOI18_werewolf) C++17
0 / 100
 264 ms 106328 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
using namespace std;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 1e9 + 7;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const int MAXN = 1e6+1;

struct UnionFind{
    vector<int> pai;
    vector<set<int>> lista;
    UnionFind(int n = 0){
        pai = vector<int>(n);
        lista = vector<set<int>>(n);
        iota(all(pai),0);
        for(int i = 0; i < n; i++)
            lista[i].insert(i);
    }
    int find(int id){
        if(pai[id] == id)
            return id;
        return pai[id] = find(pai[id]);
    }
    void onion(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b)
            return;
        if(lista[a].size() > lista[b].size())
            swap(a,b);
        pai[a] = b;
        for(int i : lista[a])
            lista[b].insert(i);
    }
};

std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    int Q = S.size();

    matrix<int> g(n);
    for(int i = 0; i < X.size(); i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }

    matrix<int>child(n);
    vector<int> pai(n);
    iota(all(pai),0);

    auto find=[&](int id){
        while(pai[id] != id)
            id = pai[id];
        return id;
    };
    auto onion =[&](int a, int b){
        a = find(a), b = find(b);
        if(a == b)
            return;
        if(a > b)
            swap(a,b);

        pai[b] = a;
        child[a].push_back(b);
    };

    auto findcond =[&](int id, int l){
        while(pai[id] != id && pai[id] >= l)
            id = pai[id];
        return id;
    };

    for(int i = n-1; i >= 0; i--){
        for(int j : g[i]){
            if(j > i)
                onion(i,j);
        }
    }

    vector<int> tin(n);
    vector<pii> range(n);
    int timer = -1;

    auto dfs =[&](int id, auto dfs)->void{
        tin[id] = ++timer;
        range[id].ff = timer;
        range[id].ss = timer;
        for(int i : child[id]){
            dfs(i,dfs);
            range[id].ss = range[i].ss;
        }
    };

    dfs(0,dfs);

    matrix<int> lift(20,vector<int>(n));
    for(int i = 0; i < n; i++){
        lift[0][i] = i;
    }
    for(int i = 0; i < 20; i++){
        for(int j = 0; j < n; j++){
            lift[i][j] = lift[i-1][lift[i-1][j]];
        }
    }

    auto getroot =[&](int id, int l){
        for(int i = 19; i >= 0; i--)
            if(lift[i][id] >= l)
                id = lift[i][id];
        return id;
    };

    matrix<int> queries(n);

    for(int i = 0; i < Q; i++){
        queries[R[i]].push_back(i);
    }

    UnionFind uf(n);

    vector<int> resp(Q);

    for(int i = 0; i < n; i++){
        //cout << i << endl;
        for(int j : g[i]){
            if(j < i)
                uf.onion(tin[i],tin[j]);
        }
        for(int q : queries[i]){
            int root = S[q];
            root = getroot(root,L[q]);
            // cout << "root(" << q << ") = " << root << '\n';
            // cout << "[" << range[root].ff << ',' << range[root].ss << "]\n";
            auto it = uf.lista[E[q]].lower_bound(tin[root]);
            resp[q] = it!=uf.lista[E[q]].end() && *it <= R[q] && *it <= range[root].ss;
            // if(resp[q]){
            //     cout << "->" << q << ' ' << *it << '\n';
            // }
        }
    }

    return resp;
}

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:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i = 0; i < X.size(); i++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:82:10: warning: variable 'findcond' set but not used [-Wunused-but-set-variable]
   82 |     auto findcond =[&](int id, int l){
      |          ^~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

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