Submission #810630

#	Time	Username	Problem	Language	Result	Execution time	Memory
810630		mrwang	Werewolf (IOI18_werewolf)	C++14	100 / 100	570 ms	167972 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=4e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,q,u[maxN],v[maxN],l[maxN],r[maxN];
vector<ll>g[maxN],a[maxN],b[maxN],v1[maxN],v2[maxN];
ll lab[maxN],lead[maxN];

ll findset(ll u)
{
    return lab[u]<0?u:lab[u]=findset(lab[u]);
}
void unite(ll u,ll v)
{
    u=findset(u);
    v=findset(v);
    if(lab[u]>lab[v]) swap(u,v);
    lab[u]+=lab[v];
    lab[v]=u;
}
ll s[maxN],t[maxN],in[maxN],out[maxN],tg=0;
set<int>ss[maxN];
void dfs(ll u)
{
    in[u]=++tg;
    for(int v:a[u])
    {
        dfs(v);
    }
    out[u]=tg;
}
vector<int> ans;
vector<pli>quer[maxN];
set<int>::iterator it;
void DFS(ll u)
{
    ss[u].insert(in[u]);
    for(int v:b[u])
    {
        DFS(v);
        if(ss[u].size()<ss[v].size()) ss[u].swap(ss[v]);
        for(auto zz:ss[v])
        {
            ss[u].insert(zz);
        }
        ss[v].clear();
    }
    for(auto cc:quer[u])
    {
        ll id=cc.fi;
        ll v=cc.se;
        it=ss[u].lower_bound(in[v]);
        if(it!=ss[u].end()&&*it<=out[v]) ans[id]=1;
        else ans[id]=0;
    }
}
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();
    for(int i=0;i<m;i++)
    {
        X[i]++;
        Y[i]++;
        g[X[i]].pb(Y[i]);
        g[Y[i]].pb(X[i]);
    }
    q=S.size();
    for(int i=0;i<q;i++)
    {
        u[i+1]=S[i]+1;
        v[i+1]=E[i]+1;
        l[i+1]=L[i];
        r[i+1]=R[i];
        l[i+1]++;
        r[i+1]++;
    }

    ans.resize(q+1);
    for(int i=1;i<=q;i++)
    {
        if(u[i]>=l[i]&&v[i]<=r[i])
        {
            v1[l[i]].pb(i);
            v2[r[i]].pb(i);
            continue;
        }
        ans[i]=0;
    }
    for(int i=1;i<=n;i++) lab[i]=-1,lead[i]=i;
    for(int i=1;i<=n;i++)
    {
        for(int j:g[i])
        {
            if(j>i) continue;
            if(findset(i)==findset(j)) continue;
            j=findset(j);
            ll x=lead[j];
            a[i].pb(x);
            unite(i,j);
        }
        lead[findset(i)]=i;
        for(auto id:v2[i])
        {
            t[id]=lead[findset(v[id])];
        }
    }
    for(int i=1;i<=n;i++) lab[i]=-1,lead[i]=i;
    for(int i=n;i>=1;i--)
    {
        for(int j:g[i])
        {
            if(j<i) continue;
            if(findset(i)==findset(j)) continue;
            j=findset(j);
            ll x=lead[j];
            b[i].pb(x);
            unite(i,j);
        }
        lead[findset(i)]=i;
        for(auto id:v1[i])
        {
            s[id]=lead[findset(u[id])];
        }
    }
    for(int i=1;i<=q;i++)
    {
        if(s[i]==0||t[i]==0) continue;
        quer[s[i]].pb({i,t[i]});
    }
    dfs(n);
    DFS(1);
    ans.erase(ans.begin());
    return ans;
}

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