Submission #136887

#	Time	Username	Problem	Language	Result	Execution time	Memory
136887		quotitquot	Werewolf (IOI18_werewolf)	C++14	0 / 100	518 ms	524288 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 = 2e5 + 1;

int trmx[4*M];
int trmn[4*M];
vector<int>g[M];
int d[M], a[M], t;
void dfs( int v, int p )
{
    d[v] = t ++;
    for( auto to: g[v] )
        if( to != p )
            dfs( to, v );
}
void bld( int v, int tl, int tr )
{
    if( tl == tr )
        trmx[v] = trmn[v] = a[tl];
    else
    {
        int tm = (tl + tr) / 2;
        bld( v*2, tl, tm );
        bld( v*2+1, tm+1, tr );
        trmx[v] = max( trmx[v*2], trmx[v*2+1] );
        trmn[v] = min( trmn[v*2], trmn[v*2+1] );
    }
}
int get_mx( int v, int tl, int tr, int l, int r )
{
    if( l > r )
        return 0;
    if( tl == l && tr == r )
        return trmx[v];
    int tm = (tl + tr) / 2;
    return max( get_mx( v*2, tl, tm, l, min(tm, r) ), get_mx( v*2+1, tm+1, tr, max(tm+1, l), r ) );
}
int get_mn( int v, int tl, int tr, int l, int r )
{
    if( l > r )
        return 1e8;
    if( tl == l && tr == r )
        return trmn[v];
    int tm = (tl + tr) / 2;
    return min( get_mn( v*2, tl, tm, l, min(tm, r) ), get_mn( v*2+1, tm+1, tr, max(tm+1, l), r ) );
}
int g_max( int l, int r, int n )
{
    return get_mx( 1, 0, n-1, l, r );
}
int g_min( int l, int r, int n )
{
    return get_mn( 1, 0, n-1, l, r );
}
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 < Q; i ++ )
    {
        if( g_min( S[i], E[i], N ) >= L[i] && g_max( S[i], E[i], N ) <= R[i] )
        {
            A[i] = 1;
            continue;
        }
        if( g_max( S[i], E[i], N ) <= R[i] )
        {
            if( a[S[i]] >= L[i] && a[S[i]] <= R[i] )
                A[i] = 1;
            else
                A[i] = 0;
            continue;
        }
        if( g_min( S[i], E[i], N ) >= L[i] )
        {
            if( a[E[i]] >= L[i] && a[E[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_min( S[i], m, N ) < L[i] )
                r = m;
            else
                l = m + 1;
        }
        if( l == S[i] )
        {
            A[i] = 0;
            continue;
        }
        if( a[l-1] < L[i] or a[i-1] > R[i] )
        {
            A[i] = 0;
            continue;
        }
        if( l == E[i] )
        {
            A[i] = 1;
            continue;
        }
        A[i] = g_max( l+1, E[i], N ) <= R[i];
    }
    return A;
}

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