Submission #928212

#	Time	Username	Problem	Language	Result	Execution time	Memory
928212		HuyQuang_re_Zero	Werewolf (IOI18_werewolf)	C++14	100 / 100	693 ms	170344 KiB

werewolf

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define maxn 200005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
using namespace std;
#include "werewolf.h"
int r[maxn],n,m,i,q,u,v,mi[maxn],ma[maxn],Begin[maxn],End[maxn],cnt,p_inc[maxn][21],p_dec[maxn][21];
set <int> s[maxn];
vector <int> a[maxn],a_inc[maxn],a_dec[maxn];
vector <II> query[maxn];
vector <int> check_validity(int n,vector <int> U,vector <int> V,vector <int> S,vector <int> T,vector <int> L,vector <int> R)
{
    m=U.size(); q=S.size();
    for(i=0;i<m;i++) U[i]++,V[i]++;
    for(i=0;i<q;i++) S[i]++,T[i]++,L[i]++,R[i]++;
    for(i=0;i<m;i++)
    {
        u=U[i]; v=V[i];
      //  cerr<<u<<" "<<v<<'\n';
        a[u].push_back(v); a[v].push_back(u);
    }


    ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // Build Inc_Tree
    function <int(int)> root=[&](int u)
    {
        return u==r[u] ? u : r[u]=root(r[u]);
    };
    auto join_inc=[&](int u,int v)
    {
        u=root(u); v=root(v);
        if(u==v) return ;
        if(mi[u]>mi[v]) swap(u,v);
        a_inc[mi[u]].push_back(mi[v]);
        mi[v]=mi[u];
        r[u]=v;
    };
    for(u=1;u<=n;u++) r[u]=mi[u]=u;
    for(u=n;u>=1;u--)
        for(int v:a[u])
            if(v>u) join_inc(u,v);


    auto join_dec=[&](int u,int v)
    {
        u=root(u); v=root(v);
        if(u==v) return ;
        if(ma[u]<ma[v]) swap(u,v);
        a_dec[ma[u]].push_back(ma[v]);
        ma[v]=ma[u];
        r[u]=v;
    };
    for(u=n;u>=1;u--) r[u]=ma[u]=u;
    for(u=1;u<=n;u++)
        for(int v:a[u])
            if(v<u) join_dec(u,v);


    function <void(int)> dfs_inc=[&](int u)
    {
        Begin[u]=++cnt;
        for(int i=1;(1<<i)<=n;i++)
            p_inc[u][i]=p_inc[p_inc[u][i-1]][i-1];
        for(int v:a_inc[u])
        {
         //   cerr<<u<<" "<<v<<'\n';
            p_inc[v][0]=u;
            dfs_inc(v);
        }
        End[u]=cnt;
    };

    function <void(int)> dfs_dec=[&](int u)
    {
        for(int i=1;(1<<i)<=n;i++)
            p_dec[u][i]=p_dec[p_dec[u][i-1]][i-1];
        for(int v:a_dec[u])
        {
          //  cerr<<u<<" "<<v<<'\n';
            p_dec[v][0]=u;
            dfs_dec(v);
        }
    };
    dfs_inc(1);
    dfs_dec(n);


    vector <int> res(q);
    function <void(int)> DFS=[&](int u)
    {
        s[u].insert(Begin[u]);
        for(int v:a_dec[u])
        {
            DFS(v);
            if(s[u].size()<s[v].size()) s[u].swap(s[v]);
            for(int k:s[v]) s[u].insert(k);
        }
        for(II x:query[u])
            res[x.snd]=(s[u].lower_bound(Begin[x.fst])!=s[u].upper_bound(End[x.fst]));
    };
    for(i=0;i<q;i++)
    {
        u=S[i]; v=T[i];
        for(int j=Log(n);j>=0;j--)
            if(p_inc[u][j]>=L[i]) u=p_inc[u][j];
        for(int j=Log(n);j>=0;j--)
            if(p_dec[v][j]>0 && p_dec[v][j]<=R[i]) v=p_dec[v][j];
       query[v].push_back({ u,i });
    }

    DFS(n);
    return res;
}
/*
int main()
{
    freopen("werewolf.inp","r",stdin);
    freopen("werewolf.out","w",stdout);
    int n,m,q,u,v,s,t,l,r,i;
    cin>>n>>m>>q;
    vector <int> U,V,S,T,L,R;
    for(i=1;i<=m;i++) cin>>u>>v,U.push_back(u),V.push_back(v);
    for(i=1;i<=q;i++) cin>>s>>t>>l>>r,S.push_back(s),T.push_back(t),L.push_back(l),R.push_back(r);
    vector <int> vec=check_validity(n,U,V,S,T,L,R);
    for(i=0;i<q;i++) cout<<vec[i]<<" ";
}
*/

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