Submission #922478

#	Time	Username	Problem	Language	Result	Execution time	Memory
922478		Alihan_8	Werewolf (IOI18_werewolf)	C++17	100 / 100	972 ms	134992 KiB

werewolf

#include <bits/stdc++.h>

#include "werewolf.h"

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                vector<int> S, vector<int> E, vector<int> L, vector<int> R){

    vector <vector<int>> adj(N);
    for ( int i = 0; i < X.size(); i++ ){
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
    }
    int n = N;
    auto gen = [&](int s){
        vector <vector<int>> tree(n);
        vector <int> fa(n);
        iota(all(fa), 0);
        auto find = [&](auto find, int u) -> int{
            return fa[u] == u ? u : fa[u] = find(find, fa[u]);
        };
        auto unite = [&](int u, int v){
            u = find(find, u), v = find(find, v);
            if ( u == v ){
                return false;
            }
            if ( u * s > v * s ){
                swap(u, v);
            }
            fa[v] = u;
            tree[u].pb(v);
            return true;
        };
        auto rng = [&](int u){
            return u >= 0 && u < n;
        };
        for ( int i = (s > 0 ? n - 1 : 0); rng(i); i -= s ){
            for ( auto &j: adj[i] ){
                if ( i * s < j * s ){
                    unite(i, j);
                }
            }
        }
        return tree;
    };
    auto wa = gen(1), wb = gen(-1);
    vector <vector<int>> upA(20, vector <int> (n)), upB(20, vector <int> (n, n - 1));
    vector <int> tin(n), tout(n);
    int ct = 0;
    auto dfs_wa = [&](auto dfs_wa, int u, int p) -> void{
        upA[0][u] = p;
        tin[u] = ++ct;
        for ( auto &v: wa[u] ){
            dfs_wa(dfs_wa, v, u);
        } tout[u] = ct;
    };
    auto dfs_wb = [&](auto dfs_wb, int u, int p) -> void{
        upB[0][u] = p;
        for ( auto &v: wb[u] ){
            dfs_wb(dfs_wb, v, u);
        }
    };
    dfs_wa(dfs_wa, 0, 0);
    dfs_wb(dfs_wb, n - 1, n - 1);
    for ( int i = 1; i < 20; i++ ){
        for ( int j = 0; j < n; j++ ){
            upA[i][j] = upA[i - 1][upA[i - 1][j]];
            upB[i][j] = upB[i - 1][upB[i - 1][j]];
        }
    }
    vector <vector<ar<int,2>>> qu(n);
    for ( int i = 0; i < S.size(); i++ ){
        int u = S[i], v = E[i];
        for ( int j = 19; j >= 0; j-- ){
            if ( upA[j][u] >= L[i] ){
                u = upA[j][u];
            }
            if ( upB[j][v] <= R[i] ){
                v = upB[j][v];
            }
        }
        qu[v].pb({u, i});
    }
    int q = S.size();
    vector <int> ans(q);
    vector <set<int>> s(n);
    auto dfs = [&](auto dfs, int u) -> void{
        s[u].insert(tin[u]);
        for ( auto &v: wb[u] ){
            dfs(dfs, v);
            if ( s[u].size() < s[v].size() ){
                swap(s[u], s[v]);
            }
            for ( auto &x: s[v] ){
                s[u].insert(x);
            } s[v].clear();
        }
        for ( auto &[v, j]: qu[u] ){
            ans[j] = s[u].lower_bound(tin[v]) != s[u].upper_bound(tout[v]);
        }
    };
    dfs(dfs, n - 1);
    return ans;
}

Compilation message (stderr)

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:37:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for ( int i = 0; i < X.size(); i++ ){
      |                      ~~^~~~~~~~~~
werewolf.cpp:99:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for ( int i = 0; i < S.size(); i++ ){
      |                      ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51