Submission #380176

#	Time	Username	Problem	Language	Result	Execution time	Memory
380176		sad	Werewolf (IOI18_werewolf)	C++14	0 / 100	460 ms	39988 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)
{
    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)
{
    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++)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;}
            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;}
        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