Submission #1280235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280235		MMihalev	Werewolf (IOI18_werewolf)	C++20	15 / 100	4100 ms	150608 KiB

werewolf

#include<iostream>
#include<vector>
#include<tuple>
#include<cmath>
#include<bitset>
#include<algorithm>
//#include "werewolf.h"
using namespace std;
const int MAX_N=2e5+5;
const int MAX_M=4e5+5;
const int NLOG=2700000;
const int BLOCK_SIZE=2400;
int n,m,q;
vector<int>g[MAX_N];
int l[MAX_N];
int r[MAX_N];
int s[MAX_N];
int e[MAX_N];

vector<int>forleft[MAX_N],forright[MAX_N],ans,comp[MAX_N];
vector<pair<int,int>>queries;
int pare[MAX_N];
///init

vector<pair<int,int>>updates1[MAX_N],updates2[MAX_N];
int upd2id[MAX_N];
int prevblockcnt[MAX_N];
bitset<MAX_N>blockqueries[NLOG/BLOCK_SIZE];
///blocks

int parent[MAX_N],sz[MAX_N];
int curtime;
int Find(int u)
{
    if(parent[u]==u)return u;
    return parent[u]=Find(parent[u]);
}
void Merge(int u,int v,bool f)
{
    int urt=Find(u),vrt=Find(v);
    if(urt==vrt)return;
    if(sz[urt]>sz[vrt])swap(urt,vrt);
    parent[urt]=vrt;
    sz[vrt]+=sz[urt];

    if(f)
    {
        for(int&node:comp[urt])
        {
            updates1[vrt].push_back({node,curtime});
        }
    }
    else
    {
        for(int&node:comp[urt])
        {
            updates2[node].push_back({vrt,curtime});
        }
    }

    for(int&node:comp[urt])comp[vrt].push_back(node);
}
///dsu

void Update(int query)
{
    int node=pare[query];
    int posr,br;
    int ll=0,rr=updates1[node].size()-1;
    while(ll<=rr)
    {
        int mid=(ll+rr)/2;
        if(updates1[node][mid].second<=r[query])
        {
            posr=mid;
            ll=mid+1;
        }
        else rr=mid-1;
    }
    br=posr/BLOCK_SIZE;
    int b;
    for(b=0;b<br;b++)
    {
        blockqueries[prevblockcnt[node]+b+1][query]=1;
    }

    int u,v,i,sz1,sz2;
    for(i=br*BLOCK_SIZE;i<=posr;i++)
    {
        u=updates1[node][i].first;
        sz2=updates2[u].size();
        while(upd2id[u]+1<sz2 && updates2[u][upd2id[u]+1].second>=l[query])
        {
            upd2id[u]++;
        }

        v=s[query];
        sz1=updates2[v].size();
        while(upd2id[v]+1<sz1 && updates2[v][upd2id[v]+1].second>=l[query])
        {
            upd2id[v]++;
        }

        if(updates2[u][upd2id[u]].second>=l[query] && updates2[v][upd2id[v]].second>=l[query] &&
           updates2[u][upd2id[u]].first==updates2[v][upd2id[v]].first)ans[query]=1;
    }
}

vector<int>nodes;
bool active[MAX_N];
bool used[MAX_N];
void dfs(int u)
{
    used[u]=1;
    for(int v:g[u])
    {
        if(v>=curtime && !used[v])dfs(v);
    }
}
void bfs(int block)
{
    int idxqueries=0,i;

    for(i=0;i<n;i++)used[i]=0;

    for(i=n-1;i>=0;i--)
    {
        if(active[i])used[i]=1;
        for(int&v:g[i])
        {
            if(v>i)
            {
                if(used[v]==used[i])continue;
                curtime=i;
                if(used[i])dfs(v);
                else dfs(i);
            }
        }

        while(idxqueries<q && i==l[idxqueries])
        {
            if(blockqueries[block][idxqueries] && used[s[idxqueries]])
            {
                ans[idxqueries]=1;
            }
            idxqueries++;
        }
    }

    for(int&u:nodes)active[u]=0;
    nodes.clear();
}

void solve()
{
    for(int i=0;i<n;i++)
    {
        parent[i]=i;
        sz[i]=i;
    }
    updates1[0].push_back({0,0});
    comp[0].push_back(0);

    for(int i=1;i<n;i++)
    {
        curtime=i;
        updates1[i].push_back({i,i});
        comp[i].push_back(i);
        for(int v:g[i])
        {
            if(v<i)
            {
                Merge(v,i,1);
            }
        }
        for(int query:forright[i])
        {
            pare[query]=Find(e[query]);
        }
    }
    int sum=0;
    for(int i=0;i<n;i++)sum+=updates1[i].size();
    if(sum>NLOG)exit(1);
    //BLOCK_SIZE=(int)(sqrt(sum));

    int curblockcnt=0;
    for(int i=0;i<=n;i++)
    {
        prevblockcnt[i]=curblockcnt;
        curblockcnt+=updates1[i].size()/BLOCK_SIZE;
    }

    for(int i=0;i<n;i++)
    {
        comp[i].clear();
        updates2[i].clear();
        parent[i]=i;
        sz[i]=i;
    }
    for(int i=n-1;i>=0;i--)
    {
        curtime=i;
        comp[i].push_back(i);
        updates2[i].push_back({i,i});
        for(int v:g[i])
        {
            if(v>i)
            {
                Merge(v,i,0);
            }
        }
    }

    for(int i=0;i<q;i++)
    {
        Update(i);
    }

    int block=1;
    for(int i=0;i<n;i++)
    {
        int posl=0,posr=BLOCK_SIZE-1;

        while(posr<updates1[i].size())
        {
            if(1)
            {
                for(int j=posl;j<=posr;j++)
                {
                    nodes.push_back(updates1[i][j].first);
                    active[updates1[i][j].first]=1;
                }
                bfs(block);
            }

            block++;
            posl+=BLOCK_SIZE;
            posr+=BLOCK_SIZE;
        }
    }
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,std::vector<int> S, std::vector<int> E,std::vector<int> L, std::vector<int> R)
{
    n=N;
    m=X.size();
    for(int i=0;i<m;i++)
    {
        int u=X[i],v=Y[i];
        g[u].push_back(v);
        g[v].push_back(u);
    }

    q=S.size();
    ans.resize(q);
    for(int i=0;i<q;i++)
    {
        queries.push_back({L[i],i});
    }
    sort(queries.rbegin(),queries.rend());

    for(int i=0;i<q;i++)
    {
        int id=queries[i].second;

        s[i]=S[id];e[i]=E[id];l[i]=L[id];r[i]=R[id];

        forleft[l[i]].push_back(i);
        forright[r[i]].push_back(i);
    }

    solve();

    auto ans2=ans;
    for(int i=0;i<q;i++)
    {
        int id=queries[i].second;
        ans[id]=ans2[i];
    }

    return ans;
}

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