Submission #791227

#	Time	Username	Problem	Language	Result	Execution time	Memory
791227		Mouad_ouj	Werewolf (IOI18_werewolf)	C++17	34 / 100	4083 ms	66508 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
vector<vector<int> > adj;
vector<int> le,ri,ind;
int smin[800001][26],smax[800001][26];
void build(int tab[],int n)
{
	for (int x=0;x<n;x++)
	{
		smin[x][0]=tab[x];
		smax[x][0]=tab[x];
	}
	for (int y=1;y<26;y++) 
	{
		for (int x=0;(x+(1<<y)-1)<n;x++)
        {		
				smin[x][y]=min(smin[x][y-1],smin[x+(1<<(y-1))][y-1]);
				smax[x][y]=max(smax[x][y-1],smax[x+(1<<(y-1))][y-1]);
        }
	}    
}
int maxn(int l,int r)
{
	int x=(int)log2(r-l+1);
	return max(smax[l][x],smax[r-(1<<x)+1][x]);
}
int minn(int l,int r)
{
	int x=(int)log2(r-l+1);
	return min(smin[l][x],smin[r-(1<<x)+1][x]);
}
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 m=x.size();
    int q=s.size();
    adj.resize(n+1);
    le.resize(n+1);
    ri.resize(n+1);
    ind.resize(n+1);
    for(int a=0;a<n;a++)
    ind[a]=-1;
    for(int a=0;a<m;a++)
    {
        adj[x[a]].push_back(y[a]);
        adj[y[a]].push_back(x[a]);
    }
    int a=0,b=0;
    for(a=0;a<n;a++)
    {
        if(adj[a].size()==1)
        break;
    }
    for(b=0;b<n;b++)
    {
        if(adj[b].size()==1 && b!=a)
        break;
    }
    ind[a]=0;
    int cur=a;
    while(cur!=b)
    {
        if(ind[adj[cur][0]]==-1)
        ind[adj[cur][0]]=ind[cur]+1,cur=adj[cur][0];
        else
        ind[adj[cur][1]]=ind[cur]+1,cur=adj[cur][1];
    }
    vector<int> ans;
    ans.resize(q);
    int tab[n];
    for(int z=0;z<n;z++)
        tab[ind[z]]=z;
    build(tab,n);
    for(int z=0;z<q;z++)
    {
        int d=0;
        if(ind[e[z]]>ind[s[z]])
        {
            if(minn(ind[s[z]],ind[e[z]])>r[z] || maxn(ind[s[z]],ind[e[z]])<l[z])
            d=0;
            else
            {
                int se=ind[s[z]],re=ind[e[z]];
                while(re>se)
                {
                    int mid=(se+re+1)/2;
                    if(minn(ind[s[z]],mid)>=l[z])
                        se=mid;
                    else
                        re=mid-1;
                }
                if(tab[se]>=l[z] && tab[se]<=r[z] && maxn(se,ind[e[z]])<=r[z])
                d=1;
                else
                d=0;
            }
        }   
        else
        {
            if(minn(ind[e[z]],ind[s[z]])>r[z] || maxn(ind[e[z]],ind[s[z]])<l[z])
            d=0;
            else
            {
                int se=ind[e[z]],re=ind[s[z]];
                while(re>se)
                {
                    int mid=(se+re)/2;
                    if(minn(mid,ind[s[z]])>=l[z])
                    re=mid;
                    else
                    se=mid+1;
                }
                if(tab[se]>=l[z] && tab[se]<=r[z] && maxn(ind[e[z]],se)<=r[z])
                d=1;
                else
                d=0;
            }
        }
        ans[z]=d;
    }
    return ans;
}

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