Submission #372342

#	Time	Username	Problem	Language	Result	Execution time	Memory
372342		denkendoemeer	Werewolf (IOI18_werewolf)	C++14	100 / 100	899 ms	151660 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int t[400005],sz[400005],l[400005],st[400005],en[400005],cur[400005],sz2[400005];
vector<int>g[400005],g2[400005],ev[400005];
set<int>nod[400005];
int n,m,q;
int findt(int x)
{
    if (x==t[x])
        return x;
    return t[x]=findt(t[x]);
}
void onion(int a,int b,bool tip)
{
    a=findt(a);
    b=findt(b);
    if (a==b)
        return ;
    if (sz[a]<sz[b])
        swap(a,b);
    if (tip==0)
        g[a].push_back(b);
    else
        for(auto it:nod[b])
            nod[a].insert(it);
    t[b]=a;
    sz[a]+=sz[b];
}
void dfs(int x)
{
    static int u=0;
    l[x]=++u;
    for(auto it:g[x])
        dfs(it);
}
vector<int>check_validity(int n2,vector<int>x,vector<int>y,vector<int>s,vector<int>e,vector<int>l2,vector<int>r)
{
    n=n2;
    m=x.size();
    q=s.size();
    vector<int>ans(q,0);
    iota(t,t+n,0);
    fill(sz,sz+n,1);
    int i;
    for(i=0;i<m;i++){
        g2[x[i]].push_back(y[i]);
        g2[y[i]].push_back(x[i]);
    }
    for(i=0;i<q;i++)
        ev[l2[i]].push_back(i);
    for(i=n-1;i>=0;i--){
        for(auto it:g2[i])
            if (i<it)
                onion(it,i,0);
        for(auto it:ev[i]){
            int nodi=findt(s[it]);
            cur[it]=nodi;
            sz2[it]=sz[nodi];
        }
        ev[i].clear();
    }
    for(i=0;i<n;i++){
        if (i==t[i]){
            dfs(i);
            break;
        }
    }
    for(i=0;i<q;i++){
        st[i]=l[cur[i]];
        en[i]=l[cur[i]]+sz2[i]-1;
        ev[r[i]].push_back(i);
    }
    for(i=0;i<n;i++)
        nod[i].insert(l[i]);
    iota(t,t+n,0);
    fill(sz,sz+n,1);
    for(i=0;i<n;i++){
        for(auto it:g2[i])
            if (it<i)
                onion(i,it,1);
        for(auto it:ev[i]){
            int nodi=findt(e[it]);
            auto it2=nod[nodi].lower_bound(st[it]);
            if (it2!=nod[nodi].end() && *(it2)<=en[it])
                ans[it]=1;
        }
    }
    return ans;
}

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