Submission #1277842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277842		k12_khoi	Werewolf (IOI18_werewolf)	C++17	49 / 100	4094 ms	46428 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>
using namespace std;

const int N=4e5+5;
const int oo=1e9+1;

int ori_n,ori_m,ori_request,n,m,request,x,y,u,v;
bool visited[N][2];
vector <int> Xvect,Yvect,Svect,Evect,Lvect,Rvect,adj[N],X,Y,S,E,L,R,ans;
queue <int> q;

namespace sub1
{
    bool bfs(int start,int goal,int Left,int Right)
    {
        while (!q.empty()) q.pop();

        for (int i=0;i<n;i++)
        visited[i][0]=visited[i][1]=false;

        visited[start][0]=true;
        q.push(start);
        while (!q.empty())
        {
            u=q.front();
            q.pop();

            if (u<n)
            {
                if (Left<=u and u<=Right)
                {
                    visited[u][1]=true;
                    q.push(u+n);
                }

                for (int v:adj[u])
                if (Left<=v and !visited[v][0])
                {
                    visited[v][0]=true;
                    q.push(v);
                }
            }
            else
            {
                u-=n;

                for (int v:adj[u])
                if (v<=Right and !visited[v][1])
                {
                    visited[v][1]=true;
                    q.push(v+n);
                }
            }
        }

        return visited[goal][1];
    }
}

namespace sub3
{
    int timer;
    int id[N],vt[N],tmiL[4*N],tmaR[4*N];

    void dfs_reid(int u,int par)
    {
        id[u]=timer;
        vt[timer]=u;

        timer++;

        for (int v:adj[u])
        if (v!=par)
            dfs_reid(v,u);
    }

    void build(int id,int l,int r)
    {
        if (l==r)
        {
            tmiL[id]=tmaR[id]=vt[l];
            return;
        }
        int m=(l+r)/2;
        build(id*2,l,m);
        build(id*2+1,m+1,r);

        tmiL[id]=min(tmiL[id*2],tmiL[id*2+1]);
        tmaR[id]=max(tmaR[id*2],tmaR[id*2+1]);
    }

    int getLeft(int id,int l,int r)
    {
        if (u>r or v<l) return oo;
        if (u<=l and v>=r) return tmiL[id];
        int m=(l+r)/2;

        return min(getLeft(id*2,l,m),getLeft(id*2+1,m+1,r));
    }

    int getRight(int id,int l,int r)
    {
        if (u>r or v<l) return -oo;
        if (u<=l and v>=r) return tmaR[id];
        int m=(l+r)/2;

        return max(getRight(id*2,l,m),getRight(id*2+1,m+1,r));
    }

    vector <int> solve()
    {
        vector <int> res;
        res.clear();

        timer=0;
        for (int i=0;i<n;i++)
        if (adj[i].size()==1)
        {
            dfs_reid(i,-1);
            break;
        }

        build(1,0,n-1);

        for (int i=0;i<request;i++)
        {
            S[i]=id[S[i]];
            E[i]=id[E[i]];
        }


        int l,r,mid,save_L,save_R;

        for (int i=0;i<request;i++)
        if (S[i]<E[i])
        {
            l=S[i];
            r=E[i];
            save_L=S[i];
            while (l<=r)
            {
                mid=(l+r)/2;

                u=S[i];
                v=mid;
                if (getLeft(1,0,n-1)>=L[i])
                {
                    save_L=mid;
                    l=mid+1;
                }
                else r=mid-1;
            }


            l=S[i];
            r=E[i];
            save_R=E[i];
            while (l<=r)
            {
                mid=(l+r)/2;

                u=mid;
                v=E[i];
                if (getRight(1,0,n-1)<=R[i])
                {
                    save_R=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }

            res.push_back(save_L>=save_R);
        }
        else
        {
            l=E[i];
            r=S[i];
            save_L=S[i];
            while (l<=r)
            {
                mid=(l+r)/2;
                u=mid;
                v=S[i];
                if (getLeft(1,0,n-1)>=L[i])
                {
                    save_L=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }


            l=E[i];
            r=S[i];
            save_R=E[i];
            while (l<=r)
            {
                mid=(l+r)/2;
                u=E[i];
                v=mid;
                if (getRight(1,0,n-1)<=R[i])
                {
                    save_R=mid;
                    l=mid+1;
                }
                else r=mid-1;
            }

            res.push_back(save_R>=save_L);
        }

        return res;
    }
}

vector <int> check_validity(int originN,vector <int> originX,vector <int> originY,vector <int> originS,vector <int> originE,vector <int> originL,vector <int> originR)
{
    n=originN;
    m=originX.size();
    request=originS.size();

    X=originX;
    Y=originY;
    for (int i=0;i<m;i++)
    {
        x=X[i];
        y=Y[i];

        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    S=originS;
    E=originE;
    L=originL;
    R=originR;

    if (m==n-1)
    {
        bool ok=true;
        for (int i=0;i<n;i++)
        if (adj[i].size()>2)
        {
            ok=false;
            break;
        }

        if (ok) return sub3::solve();
    }

    vector <int> res;
    res.clear();

    for (int i=0;i<request;i++)
    res.push_back(sub1::bfs(S[i],E[i],L[i],R[i]));

    return res;
}

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