Submission #310627

#	Time	Username	Problem	Language	Result	Execution time	Memory
310627		vipghn2003	Werewolf (IOI18_werewolf)	C++14	100 / 100	1060 ms	151548 KiB

werewolf

#include <bits/stdc++.h>

using namespace std;

const int N=4e5+5;
int n,m,q,par[N],sz[N],l[N],st[N],en[N],now[N],nsz[N];
vector<int>adj[N],g[N],event[N];
set<int>node[N];

int Find(int u)
{
    if(par[u]==u) return u;
    return par[u]=Find(par[u]);
}

void Union(int u,int v,bool type)
{
    u=Find(u);
    v=Find(v);
    if(u==v) return;
    if(sz[u]<sz[v]) swap(u,v);
    if(!type) g[u].push_back(v);
    else for(auto&it:node[v]) node[u].insert(it);
    par[v]=u;
    sz[u]+=sz[v];
}

void dfs(int u)
{
    static int nTime=0;
    l[u]=++nTime;
    for(auto &v:g[u]) dfs(v);
}

vector<int>check_validity(int _n,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R)
{
    n=_n;
    m=X.size();
    q=S.size();
    vector<int>res(q,0);
    iota(par,par+n,0);
    fill(sz,sz+n,1);
    for(int i=0;i<m;i++)
    {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    for(int i=0;i<q;i++) event[L[i]].push_back(i);
    for(int i=n-1;i>=0;i--)
    {
        for(auto&e:adj[i]) if(e>i) Union(e,i,0);
        for(auto&id:event[i])
        {
            int u=Find(S[id]);
            now[id]=u;
            nsz[id]=sz[u];
        }
        event[i].clear();
    }
    for(int i=0;i<n;i++)
    {
        if(par[i]==i)
        {
            dfs(i);
            break;
        }
    }
    for(int i=0;i<q;i++)
    {
        st[i]=l[now[i]];
        en[i]=l[now[i]]+nsz[i]-1;
        event[R[i]].push_back(i);
    }
    for(int i=0;i<n;i++) node[i].insert(l[i]);
    iota(par,par+n,0);
    fill(sz,sz+n,1);
    for(int i=0;i<n;i++)
    {
        for(auto&j:adj[i]) if(j<i) Union(i,j,1);
        for(auto&id:event[i])
        {
            int u=Find(E[id]);
            auto it=node[u].lower_bound(st[id]);
            if(it!=node[u].end()&&*(it)<=en[id]) res[id]=1;
        }
    }
    return res;
}

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