Submission #108953

#	Time	Username	Problem	Language	Result	Execution time	Memory
108953		boatinw99	Werewolf (IOI18_werewolf)	C++11	100 / 100	3550 ms	121588 KiB

werewolf

/**
 *      Author : boatinw99
 *      Date : 3.5.2019 15:42
 */

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std ;
typedef pair<int,int> pii ;
#define fi first
#define se second
const int N = 2e5+9 ,inf = 1e9 ;
struct Q
{
    int st,ed,l,r,idx ;
}query[N];
unordered_map<int,int> mp[N];
vector<int> memb[N];
pii edge[N<<1] ;
int n,m,q,p1[N],p2[N],sz[N],up[N];
int find(int u)
{
    while(p1[u])u=p1[u];
    return u ;
}
void Union(int u,int v)
{
    int mn = min(u,v);
    u=find(u),v=find(v);
    if(u==v)return ;
    if(sz[u]>sz[v])swap(u,v);
    p1[u]=v;
    sz[v]+=sz[u];
    up[u]=mn;
}
void constructdsu()
{
    for(int i=1;i<=n;i++)
    {
        p2[i]=i;
        sz[i]=1;
        memb[i].push_back(i);
    }
    sort(edge+1,edge+1+m,[&](const pii a,const pii b){
        return min(a.fi,a.se)>min(b.fi,b.se);});
    for(int i=1;i<=m;i++)Union(edge[i].fi,edge[i].se);
    for(int i=1;i<=n;i++)
    {
        int node = i , dist = inf ;
        while(node)
        {
            mp[node][i]=dist;
            dist=min(dist,up[node]);
            node=p1[node];
        }
    }
}
void magic_Union(int u,int v)
{
    u=p2[u],v=p2[v];
    if(u==v)return ;
    if(memb[u].size()>memb[v].size())swap(u,v);
    for(auto it:memb[u])
    {
        p2[it]=v;
        int node = it;
        while(node)
        {
            auto its = mp[node].find(u);
            if(its==mp[node].end())break ;
            mp[node][v]=max(mp[node][v],its->se);
            mp[node].erase(its);
            node=p1[node];
        }
        memb[v].push_back(it);
    }
}
vector<int> check_validity(int SZ,vector<int> X,vector<int> Y,
                                vector<int> S,vector<int> E,
                                vector<int> L,vector<int> R)
{
    n=SZ;
    m=X.size();
    q=S.size();
    vector<int> ans(q);
    for(int i=1;i<=m;i++)edge[i]={X[i-1]+1,Y[i-1]+1};
    for(int i=1;i<=q;i++)query[i]={S[i-1]+1,E[i-1]+1,L[i-1]+1,R[i-1]+1,i};
    constructdsu();
    ///Done preprocess
    sort(query+1,query+1+q,[&](const Q a,const Q b){
         return a.r<b.r;});
    sort(edge+1,edge+1+m,[&](const pii a,const pii b){
         return max(a.fi,a.se)<max(b.fi,b.se);});
    for(int i=1,j=1;i<=q;i++)
    {
        while(j<=m&&max(edge[j].fi,edge[j].se)<=query[i].r)
        {
            magic_Union(edge[j].fi,edge[j].se);
            j++;
        }
        int st = query[i].st , ed = query[i].ed , mnup = inf , dist = 0;
        while(st)
        {
            auto its = mp[st].find(p2[ed]);
            if(its!=mp[st].end())dist=max(dist,min(mnup,mp[st][p2[ed]]));
            ///printf("aa %d %d | %d\n",dist,mnup,mp[st][p2[ed]]);
            mnup=min(mnup,up[st]);
            st=p1[st];
        }
        ans[query[i].idx-1]=(p2[query[i].st]==p2[query[i].ed]||dist>=query[i].l);
    }
    return ans ;
}

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