Submission #298057

#	Time	Username	Problem	Language	Result	Execution time	Memory
298057		muhammad_hokimiyon	Werewolf (IOI18_werewolf)	C++14	15 / 100	3194 ms	172924 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define dl double long

const int maxn = 200200;

int n,m,q;
int tim;
int t[4 * maxn];
int tin1[maxn];
int tout1[maxn];
int tin2[maxn];
int tout2[maxn];
int p[maxn];
int o1[maxn];
int o2[maxn];
int d1[maxn][25];
int d2[maxn][25];
vector < int > g[maxn];
vector < int > v[maxn];
vector < pair < int , int > > gg[maxn];

void upd( int x , int l , int r , int p , int val )
{
    v[x].push_back(val);
    if( l == r ){
        return;
    }
    int m = (l + r) / 2;
    if( p <= m )upd( x + x , l , m , p , val );
    else upd( x + x + 1 , m + 1 , r , p , val );
}

int get1( int x , int l , int r , int tl , int tr , int tl1 , int tr1 )
{
    if( tl > tr )return 0;
    if( l == tl && r == tr ){
        int y = (int)(lower_bound( v[x].begin() , v[x].end() , tl1 ) - v[x].begin());
        if( y != (int)v[x].size() && v[x][y] <= tr1 )return 1;
        return 0;
    }
    int m = (l + r) / 2;
    return ( get1( x + x , l , m , tl , min( tr , m ) , tl1 , tr1 ) |
               get1( x + x + 1 , m + 1 , r , max( tl , m + 1 ) , tr , tl1 , tr1 ) );
}

int get( int x )
{
    return (p[x] == x ? x : p[x] = get(p[x]));
}

void meg( int x , int y )
{
    int px = get(x);
    int py = get(y);
    if( px == py )return;
    p[px] = py;
    g[py].push_back(px);
    g[px].push_back(py);
}

void dfs( int x , int p )
{
    d1[x][0] = p;
    for( int i = 1; i < 25; i++ ){
        d1[x][i] = d1[d1[x][i - 1]][i - 1];
    }
    tin1[x] = ++tim;
    o1[tim] = x;
    for( auto y : g[x] ){
        if( y == p )continue;
        dfs( y , x );
    }
    tout1[x] = tim;
}

int ff( int x , int y )
{
    for( int i = 24; i >= 0; i-- ){
        if( d2[x][i] <= y ){
            x = d2[x][i];
        }
    }
    return x;
}

int ff1( int x , int y )
{
    for( int i = 24; i >= 0; i-- ){
        if( d1[x][i] >= y ){
            x = d1[x][i];
        }
    }
    return x;
}

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;
    m = (int)X.size();
    q = (int)S.size();
    for( int i = 1; i <= n; i++ ){
        p[i] = i;
    }
    for( int i = 0; i < m; i++ ){
        v[X[i]].push_back(Y[i]);
        v[Y[i]].push_back(X[i]);
    }
    for( int i = 0; i < n; i++ ){
        for( auto x : v[i] ){
            if( x > i )continue;
            meg( x , i );
        }
    }
    dfs( n - 1 , n - 1 );
    for( int i = 0; i <= n; i++ ){
        tin2[i] = tin1[i];
        tout2[i] = tout1[i];
        o2[i] = o1[i];
        g[i].clear();
        p[i] = i;
        for( int j = 0; j < 25; j++ ){
            d2[i][j] = d1[i][j];
        }
    }
    tim = 0;
    for( int i = n - 1; i >= 0; i-- ){
        for( auto x : v[i] ){
            if( x < i )continue;
            meg( x , i );
        }
    }
    dfs( 0 , 0 );
    for( int i = 0; i < q; i++ ){
        gg[R[i]].push_back({L[i] , i});
    }
    vector < int > ans(q , -1);
    for( int i = 0; i < n; i++ ){
        upd( 1 , 0 , n , tin2[i] , tin1[i] );
        for( auto x : gg[i] ){
            int yy = ff( E[x.se] , i );
            int y = ff1( S[x.se] , x.fi );
            bool f = false;
            for( int j = tin2[yy]; j <= tout2[yy]; j++ ){
                for( int h = tin1[y]; h <= tout1[y]; h++ ){
                    f |= (o2[j] == o1[h]);
                }
            }
            ans[x.se] = f;
        }
    }
    return ans;
}

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