Submission #1280105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280105		MMihalev	Werewolf (IOI18_werewolf)	C++20	15 / 100	3599 ms	589824 KiB

werewolf

#include<iostream>
#include<vector>
#include<tuple>
#include "werewolf.h"
using namespace std;
const int MAX_N=2e5+5;
const int MAX_M=4e5+5;
const int BLOCK_SIZE=5000;
int n,m,q;
vector<int>g[MAX_N];
struct qq
{
    int l,r,s,e,id;
};
vector<qq>forleft[MAX_N],forright[MAX_N],queries;
vector<tuple<int,int,int>>checkone[MAX_N];
int pare[MAX_N];
///init

vector<pair<int,int>>updates[MAX_N];
int prevblockcnt[MAX_N];
vector<tuple<int,int,int>>blockqueries[MAX_N];
///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)return;
    for(auto [node,useless]:updates[urt])
    {
        updates[vrt].push_back({node,curtime});
    }
}
///dsu

void Update(qq query)
{
    int node=pare[query.id];
    int posr,br;
    int l=0,r=updates[node].size()-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(updates[node][mid].second<=query.r)
        {
            posr=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    br=posr/BLOCK_SIZE;

    for(int b=0;b<br;b++)
    {
        blockqueries[prevblockcnt[node]+b+1].push_back({query.l,query.s,query.id});
    }

    for(int i=br*BLOCK_SIZE;i<=posr;i++)
    {
        checkone[query.l].push_back({updates[node][i].first,query.s,query.id});
    }
}

vector<int>nodes;
vector<int>ans;
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;

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

    for(int i=n-1;i>=0;i--)
    {
        while(idxqueries+1<blockqueries[block].size() && get<0>(blockqueries[block][idxqueries])>i)idxqueries++;

        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);
            }
        }

        if(i==get<0>(blockqueries[block][idxqueries]))
        {
            if(used[get<1>(blockqueries[block][idxqueries])])
            {
                ans[get<2>(blockqueries[block][idxqueries])]=1;
            }
        }
    }

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

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

    for(int i=1;i<n;i++)
    {
        curtime=i;
        updates[i].push_back({i,i});
        for(int v:g[i])
        {
            if(v<i)
            {
                Merge(v,i,1);
            }
        }
        for(auto query:forright[i])
        {
            pare[query.id]=Find(query.e);
        }
    }

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

    for(int i=n-1;i>=0;i--)
    {
        for(auto query:forleft[i])Update(query);
    }
    ///make queries

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

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

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

    for(int i=0;i<n;i++)
    {
        parent[i]=i;
        sz[i]=i;
    }
    for(int i=n-1;i>=0;i--)
    {
        for(int v:g[i])
        {
            if(v>i)
            {
                Merge(v,i,0);
            }
        }
        for(auto que:checkone[i])
        {
            int u,v,id;
            tie(u,v,id)=que;
            if(Find(u)==Find(v))ans[id]=1;
        }
    }
    //single node queries
    ///solve queries
}

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++)
    {
        qq cur;cur.s=S[i];cur.e=E[i];cur.l=L[i];cur.r=R[i];cur.id=i;
        forleft[L[i]].push_back(cur);
        forright[R[i]].push_back(cur);
        queries.push_back(cur);
    }

    solve();

    return ans;
}

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