Submission #136884

#	Time	Username	Problem	Language	Result	Execution time	Memory
136884		quotitquot	Werewolf (IOI18_werewolf)	C++14	0 / 100	485 ms	524292 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
#define ll long long
#define fr fisrt
#define se second
#define pb push_back
using namespace std;

const ll M = 20;
const ll N_M = 2e5 + 1;

int mx[N_M][M];
int mn[N_M][M];
vector<int>g[N_M];
int d[N_M], a[N_M], s[N_M], t;
void dfs( int v, int p )
{
    d[v] = t ++;
    for( auto to: g[v] )
        if( to != p )
            dfs( to, v );
}
int g_max( int l, int r )
{
    int m = d[r-l+1];
    int mi = r - (1 << m) + 1;
    return max( mx[l][m], mx[mi][m] );
}
int g_min( int l, int r )
{
    int m = d[r-l+1];
    int mi = r - (1 << m) + 1;
    return min( mn[l][m], mn[mi][m] );
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    int Q = S.size();
    vector<int> A(Q);
    for( int i = 0; i < int(X.size()); i ++ )
    {
        g[X[i]].pb( Y[i] );
        g[Y[i]].pb( X[i] );
    }
    int st = 0;
    for( int i = 0; i < N; i ++ )
        if( int(g[i].size()) == 1 )
            st = i;
    dfs( st, st );
    for( int i = 0; i < N; i ++ )
        a[d[i]] = i;
    for( int i = 0; i < Q; i ++ )
    {
        S[i] = d[S[i]];
        E[i] = d[E[i]];
        if( S[i] > E[i] )
            swap( S[i], E[i] );
    }
    for( int i = 0; i < M; i ++ )
    {
        int h = (1 << i);
        if( h >= N )
            break;
        s[h] = 1;
    }
    for( int i = 1; i < N; i ++ )
        s[i] += s[i-1];
    for( int i = 0; i < N; i ++ )
        mx[i][0] = mn[i][0] = a[i];
    for( int i = 0; i < N; i ++ )
    {
        for( int j = 1; j < M; j ++ )
        {
            int h1 = (1 << j);
            int h2 = (1 << (j-1));
            if( i+h1-1 >= N )
                break;
            mx[i][j] = max( mx[i][j-1], mx[i+h2][j-1] );
            mn[i][j] = min( mn[i][j-1], mn[i+h2][j-1] );
        }
    }
    for( int i = 0; i < Q; i ++ )
    {
        if( g_min( S[i], E[i] ) >= L[i] && g_max( S[i], E[i] ) <= R[i] )
        {
            A[i] = 1;
            continue;
        }
        if( g_max( S[i], E[i] ) <= R[i] )
        {
            if( a[E[i]] >= L[i] && a[E[i]] <= R[i] )
                A[i] = 1;
            else
                A[i] = 0;
            continue;
        }
        if( g_min( S[i], E[i] ) >= L[i] )
        {
            if( a[S[i]] >= L[i] && A[S[i]] <= R[i] )
                A[i] = 1;
            else
                A[i] = 0;
            continue;
        }
        int l = S[i], r = E[i], m;
        while( l < r )
        {
            m = (l + r) / 2;
            if( g_max( S[i], m ) > R[i] )
                r = m;
            else
                l = m + 1;
        }
        if( l == S[i] )
        {
            A[i] = 0;
            continue;
        }
        if( !(a[l-1] >= L[i] && a[l-1] <= L[i]) )
        {
            A[i] = 0;
            continue;
        }
        if( l == E[i] )
        {
            A[i] = 1;
            continue;
        }
        A[i] = g_min( l+1, E[i] ) > L[i];
    }
    return A;
}

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