Submission #115077

#	Time	Username	Problem	Language	Result	Execution time	Memory
115077		zoooma13	Werewolf (IOI18_werewolf)	C++14	0 / 100	540 ms	36668 KiB

werewolf

#include "werewolf.h"
//#include "grader.cpp"
#include "bits/stdc++.h"
using namespace std;

#define MAX_N 200005
#define FL (p<<1)|1
#define FR (p<<1)+2

int n ,m ,q;
vector <int> adj[MAX_N];

int pos[MAX_N];
vector <int> a;

void go(int u ,int p=-1){
    pos[u] = a.size();
    a.push_back(u);
    for(int&v : adj[u])
        if(v != p)
            go(v ,u);
}

pair<int ,int> mix(pair<int ,int>a ,pair<int ,int>b){
    a.first = min(a.first ,b.first);
    a.second = max(a.second ,b.second);
    return a;
}
int tmx[4*MAX_N] ,tmn[4*MAX_N];
void build(int l=0 ,int r=n-1 ,int p=0){
    if(l == r){
        tmx[p] = tmn[p] = a[l];
        return;
    }
    int mid = (l+r)>>1;
    build(l ,mid ,FL);
    build(mid+1 ,r ,FR);
    tmx[p] = max(tmx[FL] ,tmx[FR]);
    tmn[p] = max(tmn[FL] ,tmn[FR]);
}
pair <int ,int> query(int ql ,int qr ,int l=0 ,int r=n-1 ,int p=0){
    if(ql <= l && r <= qr)
        return {tmn[p] ,tmx[p]};
    if(r < ql || qr < l)
        return {1e9 ,-1e9};
    int mid = (l+r)>>1;
    return mix(query(ql ,qr ,l ,mid ,FL) ,query(ql ,qr ,mid+1 ,r ,FR));
}
int lasth(int ql ,int qr ,int v ,int l=0 ,int r=n-1 ,int p=0){
    if(r < ql || qr < l)
        return -1;
    if(l == r)
        return l;
    int mid = (l+r)>>1;
    if(ql <= l && r <= qr){
        if(tmx[FR] >= v)
            return lasth(ql ,qr ,v ,mid+1 ,r ,FR);
        if(tmx[FL] >= v)
            return lasth(ql ,qr ,v ,l ,mid ,FL);
        return -1;
    }
    int op = lasth(ql ,qr ,v ,mid+1 ,r ,FR);
    if(~op)
        return op;
    return lasth(ql ,qr ,v ,l ,mid ,FL);
}

bool both(int x ,int l ,int r){
    return l <= x && x <= 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)
{
    n = N ,m = X.size() ,q = S.size();
    assert(m == n-1);
    for(int i=0; i<m; i++)
        adj[X[i]].push_back(Y[i]),
        adj[Y[i]].push_back(X[i]);
    for(int i=0; i<n; i++)
        if(adj[i].size() == 1){
            go(i);
            break;
        }

    build();

    vector <int> A(q ,0);
    for(int i=0; i<q; i++){
        if(pos[S[i]] > pos[E[i]])
            swap(S[i] ,E[i]);

        int lh = lasth(pos[S[i]] ,pos[E[i]] ,L[i]);
        if(~lh && lh < pos[E[i]] && both(a[lh+1] ,L[i] ,R[i])){
            auto p1 = query(pos[S[i]] ,lh);
            auto p2 = query(lh+1 ,pos[E[i]]);
            if(p1.first >= L[i] && p2.second <= R[i])
                A[i] = 1;
        }
        if(~lh && lh <= pos[E[i]] && both(a[lh] ,L[i] ,R[i])){
            auto p1 = query(pos[S[i]] ,lh);
            if(p1.first >= L[i])
                A[i] = 1;
        }
    }

    return A;
}

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