Submission #366614

#	Time	Username	Problem	Language	Result	Execution time	Memory
366614		denkendoemeer	Werewolf (IOI18_werewolf)	C++14	49 / 100	641 ms	69616 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int m,q,h[200005],mini[200005][20],maxi[200005][20],cnt;
vector<int>g[200005],sol;
bool viz[200005],na[200005],v[200005],ok;
void dfs(int nod,int t)
{
    viz[nod]=1;
    for(auto it:g[nod]){
        if (viz[it]==0 && it<=t)
            dfs(it,t);
    }
}
void dfs2(int nod,int t)
{
    na[nod]=1;
    for(auto it:g[nod]){
        if (na[it]==0 && it>=t)
            dfs2(it,t);
    }
}
void dfs3(int nod)
{
    v[nod]=1;
    mini[cnt][0]=nod;
    maxi[cnt][0]=nod;
    h[nod]=cnt;
    cnt++;
    for(auto it:g[nod])
        if (v[it]==0)
            dfs3(it);
}
vector<int> check_validity(int n,vector<int>x,vector<int>y,vector<int>s,vector<int>e,vector<int>l,vector<int>r)
{
    m=x.size();
    q=s.size();
    int i,j;
    for(i=0;i<m;i++)
        g[x[i]].push_back(y[i]),g[y[i]].push_back(x[i]);
    if (n<=3000 && q<=3000){
        for(i=0;i<q;i++){
            ok=0;
            int j;
            for(j=0;j<n;j++)
                viz[j]=0,na[j]=0;
            dfs(e[i],r[i]);
            dfs2(s[i],l[i]);
            for(j=0;j<n;j++)
                if (viz[j] && na[j])
                    ok=1;
            sol.push_back(ok);
        }
        return sol;
    }
    for(i=0;i<n;i++)
        if (v[i]==0 && g[i].size()==1)
            dfs3(i);
    for(j=1;j<20;j++)
        for(i=0;i<n;i++){
            int auxi=min(n-1,i+(1<<(j-1)));
            mini[i][j]=min(mini[i][j-1],mini[auxi][j-1]);
            maxi[i][j]=max(maxi[i][j-1],maxi[auxi][j-1]);
        }
    for(i=0;i<q;i++){
        int a=h[s[i]],b=h[e[i]];
        if (a<b){
            for(j=19;j>=0;j--)
                if (a<n && mini[a][j]>=l[i])
                    a=a+(1<<j);
            for(j=19;j>=0;j--){
                int x=max(0,b-(1<<j)+1);
                if (maxi[x][j]<=r[i])
                    b=x-1;
            }
            if (a>=n || b==-1 || a-b>1)
                sol.push_back(1);
            else
                sol.push_back(0);
        }
        else{
            for(j=19;j>=0;j--)
                if (b<n && maxi[b][j]<=r[i])
                    b+=(1<<j);
            for(j=19;j>=0;j--){
                int x=max(0,a-(1<<j)+1);
                if (mini[x][j]>=l[i])
                    a=x-1;
            }
            if (b>=n || a==-1 || b-a>1)
                sol.push_back(1);
            else
                sol.push_back(0);
        }
    }
    return sol;
}

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