Submission #295834

#	Time	Username	Problem	Language	Result	Execution time	Memory
295834		daniel920712	Werewolf (IOI18_werewolf)	C++14	49 / 100	2392 ms	57848 KiB

werewolf

#include "werewolf.h"
#include <queue>
#include <vector>
#include <stdio.h>
using namespace std;
queue < pair < int , int > > all;
vector < int > Next[200005];
bool have[5][200005];
int con[200005]={0};
int what[200005];
int cha[200005],now=1;
struct A
{
    int l,r;
    int nxl,nxr;
    int big,small;
}Node[2000005];
void F(int here,int fa,int deg)
{
    what[deg]=here;
    cha[here]=deg;
    for(auto i:Next[here]) if(i!=fa) F(i,here,deg+1);
}
void build(int l,int r,int here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].nxl=now++;
    Node[here].nxr=now++;
    if(l==r)
    {
        Node[here].big=what[l];
        Node[here].small=what[l];
        return ;
    }
    Node[here].nxl=now++;
    Node[here].nxr=now++;
    build(l,(l+r)/2,Node[here].nxl);
    build((l+r)/2+1,r,Node[here].nxr);
    Node[here].big=max(Node[Node[here].nxl].big,Node[Node[here].nxr].big);
    Node[here].small=min(Node[Node[here].nxl].small,Node[Node[here].nxr].small);
}
int Find1(int l,int r,int here)
{
    if(Node[here].l==l&&Node[here].r==r) return Node[here].small;
    if(r<=(Node[here].l+Node[here].r)/2) return Find1(l,r,Node[here].nxl);
    if(l>(Node[here].l+Node[here].r)/2) return Find1(l,r,Node[here].nxr);
    else return min(Find1(l,(Node[here].l+Node[here].r)/2,Node[here].nxl),Find1((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr));
}
int Find2(int l,int r,int here)
{
    if(Node[here].l==l&&Node[here].r==r) return Node[here].big;
    if(r<=(Node[here].l+Node[here].r)/2) return Find2(l,r,Node[here].nxl);
    if(l>(Node[here].l+Node[here].r)/2) return Find2(l,r,Node[here].nxr);
    else return max(Find2(l,(Node[here].l+Node[here].r)/2,Node[here].nxl),Find2((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr));
}
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(),M=X.size(),i,j,ok,a,b,l,r;
    vector<int> A(Q);
    vector<int> B(Q);
    for(i=0;i<M;i++)
    {
        Next[X[i]].push_back(Y[i]);
        Next[Y[i]].push_back(X[i]);
        con[X[i]]++;
        con[Y[i]]++;
    }
    if(N<=3000)
    {
        for(i=0;i<Q;i++)
        {
            //if(S[i]!=83069||S[i])
            for(j=0;j<N;j++) have[0][j]=have[1][j]=0;
            ok=0;
            all.push(make_pair(S[i],0));
            while(!all.empty())
            {
                a=all.front().first;
                b=all.front().second;
                all.pop();
                if(a==E[i]&&b==1)
                {
                    ok=1;
                    break;
                }
                if(have[b][a]) continue;
                if(b==0&&a<L[i]) continue;
                if(b==1&&a>R[i]) continue;
                have[b][a]=1;

                if(b==0&&a>=L[i]&&a<=R[i]) all.push(make_pair(a,1));

                for(auto i:Next[a]) all.push(make_pair(i,b));
            }
            while(!all.empty()) all.pop();
            A[i]=ok;
            B[i]=ok;
            //printf("%d ",ok);
            //printf("\n");

        }
        //printf("\n");
    }
    else
    {
        for(i=0;i<N;i++)
        {
            if(con[i]==1)
            {
                all.push(make_pair(i,-1));
                for(j=0;j<N;j++)
                {
                    what[j]=all.front().first;
                    cha[all.front().first]=j;
                    for(auto k:Next[all.front().first]) if(k!=all.front().second) all.push(make_pair(k,all.front().first));
                    all.pop();
                }
                break;
            }
        }
        build(0,N-1,0);
        for(i=0;i<Q;i++)
        {
            a=cha[S[i]];
            b=cha[E[i]];
            //printf("%d %d\n",a,b);
            if(what[a]<L[i])
            {
                A[i]=0;
                continue;
            }
            if(what[b]>R[i])
            {
                A[i]=0;
                continue;
            }
            if(a<b)
            {
                l=a;
                r=b+1;
                while((r-l)>1)
                {
                    if(Find1(a,(l+r)/2,0)>=L[i]) l=(l+r)/2;
                    else r=(l+r)/2;
                }

                if(what[l]<L[i]) l--;
                if(Find2(l,b,0)<=R[i]) A[i]=1;
                else A[i]=0;
            }
            else
            {
                l=b;
                r=a;
                while((r-l)>1)
                {
                    if(Find1((l+r)/2,a,0)>=L[i]) r=(l+r)/2;
                    else l=(l+r)/2;
                }

                if(what[l]<L[i]) l++;

                if(Find2(b,l,0)<=R[i]) A[i]=1;
                else A[i]=0;
            }
        }
    }
    /*for(i=0;i<Q;i++)
    {
        if(A[i]!=B[i])
        {

            printf("%d %d %d %d %d %d %d\n",i,A[i],B[i],cha[S[i]],cha[E[i]],S[i],E[i]);
            printf("%d %d\n",L[i],R[i]);
            for(j=cha[S[i]];j<=cha[E[i]];j++) printf("%d ",what[j]);
        }
    }*/



    return A;
}

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