Submission #380197

#	Time	Username	Problem	Language	Result	Execution time	Memory
380197		sad	Werewolf (IOI18_werewolf)	C++14	0 / 100	357 ms	39908 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int n;
const int N=200090;
int idx[N],vis[N],a[N],treemn[N*4],treemx[N*4];
vector<int>v[N];
void go (int x,int y)
{
    idx[x]=y;
    a[y]=x;
    vis[x]=1;
    for(auto it:v[x])
    {
        if(vis[it])
            continue;
        go(it,y+1);
    }
}
int get1 (int ind,int st,int end,int l,int r,int x)
{
    for(int i=l; i<=r; i++)
    {
        if(a[i]>x)
            return i-1;
    }
    return r;
    if(r<l)
        return 0;
    if(l>end||r<st)
        return (end-st+1);
    int m=(st+end )/2;
    int re=0;
    if(l<=st&&end<=r)
    {

        if(st==end&&a[st]<=x)
            return 1;
        else if(st==end)
            return 0;
        if(treemx[ind]<=x)
            return (end-st+1);
        if(treemx[ind*2+1]<=x)
        {
            re=get1(ind*2+2,m+1,end,l,r,x);
            re+=m+1-st;
            return re;
        }
        re=get1(ind*2+1,st,m,l,r,x);
        return re;
    }
    re=get1(ind*2+1,st,m,l,r,x);
    if(re==m+1-st)
    {
        re+=get1(ind*2+2,m+1,end,l,r,x);
        return re;
    }
    return re;
}
int get (int ind,int st,int end,int l,int r,int x)
{
    for(int i=l; i<=r; i++)
    {
        if(a[i]<x)
            return i-1;
    }
    return r;
    if(r<l)
        return 0;
    if(l>end||r<st)
        return (end-st+1);
    int m=(st+end )/2;
    int re=0;
    if(l<=st&&end<=r)
    {
        if(st==end&&a[st]>=x)
            return 1;
        else if(st==end)
            return 0;
        if(treemn[ind]>=x)
            return (end-st+1);
        if(treemn[ind*2+1]>=x)
        {
            re=get(ind*2+2,m+1,end,l,r,x);
            re+=m+1-st;
            return re;
        }
        re=get(ind*2+1,st,m,l,r,x);
        return re;
    }
    re=get(ind*2+1,st,m,l,r,x);
    if(re==m+1-st)
    {
        re+=get(ind*2+2,m+1,end,l,r,x);
        return re;
    }
    return re;
}
void build(int ind,int st,int end)
{
    if(st==end)
    {
        treemx[ind]=a[st];
        treemn[ind]=a[st];
        return;
    }
    int m=(st+end)/2;
    build(ind*2+1,st,m);
    build(ind*2+2,m+1,end);
    treemn[ind]=min(treemn[ind*2+1],treemn[ind*2+2]);
    treemx[ind]=max(treemx[ind*2+1],treemx[ind*2+2]);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,
                           vector<int> L, vector<int> R)
{
    memset(a,0,sizeof a);
    memset(treemn,0,sizeof treemn);
    memset(treemx,0,sizeof treemx);
    memset(idx,0,sizeof idx);
    for(int i=0; i<n+3; i++)
        a[i]=n+1;
    for(int i=0; i<n+3; i++)
        v[i].clear();
    n=N;
    int m=X.size();
    for(int i=0; i<m; i++)
    {
        v[X[i]].pb(Y[i]);
        v[Y[i]].pb(X[i]);
    }
    int st=0;
    for(int i=0; i<n; i++)
    {
        if(v[i].size()==1)
        {
            st=i;
            break;
        }
    }
    vector<int>ans;
    ans.clear();
    go(st,1);
    build(0,1,n);
    int q=S.size();
    for(int i=0; i<q; i++)
    {
        int s=S[i],e=E[i],l=L[i],r=R[i];
        if(s<l||e>r)
        {
            ans.pb(0);
            continue;
        }
        if(idx[s]>idx[e])
        {
            swap(s,e);
            int x=get1(0,1,n,idx[s],n,r);
            if(x>=idx[e])
            {
                ans.pb(1);
                continue;
            }
            if(a[x]<l)
            {
                ans.pb(0);
                continue;
            }
            x+=get(0,1,n,x,n,l);
            if(x>=idx[e])
                ans.pb(1);
            else
                ans.pb(0);
            continue;
        }
        int x=get(0,1,n,idx[s],n,l);
        if(x>=idx[e])
        {
            ans.pb(1);
            continue;
        }
        if(a[x]>r)
        {
            ans.pb(0);
            continue;
        }
        x+=get1(0,1,n,x,n,r);
        if(x>=idx[e])
            ans.pb(1);
        else
            ans.pb(0);
    }
    return ans;
}

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