Submission #1220583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220583		LeonidCuk	Werewolf (IOI18_werewolf)	C++20	100 / 100	585 ms	120520 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
struct krt
{
    vector<vector<int>>g,lca;
    vector<int>dsu,el,er;
    int timer=0;
    int vfind(int a)
    {
        if(a==dsu[a])return a;
        return dsu[a]=vfind(dsu[a]);
    }
    void kmerge(int a,int b,bool k)
    {
        int a1=vfind(a),b1=vfind(b);
        if(a1!=b1)
        {
            if(a1>b1&&k)swap(a1,b1);
            else if(k==0&&a1<b1)swap(a1,b1);
            dsu[a1]=b1;
            g[b1].push_back(a1);
        }
    }
    void dfs(int a,int b)
    {
        el[a]=timer;timer++;
        lca[a][0]=b;
        for(int i=1;i<20;i++)
        {
            lca[a][i]=lca[lca[a][i-1]][i-1];
        }
        for(auto i:g[a])
        {
            dfs(i,a);
        }
        er[a]=timer-1;
    }
    krt(int n)
    {
        dsu.resize(n);
        g.resize(n);
        lca.resize(n,vector<int>(20));
        el.resize(n);
        er.resize(n);
        for(int i=0;i<n;i++)dsu[i]=i;
    }
};
vector<int>st;
void update(int i,int l,int r,int x)
{
    if(l==r)st[i]=1;
    else
    {
        int m=(l+r)/2;
        if(x<=m)update(2*i,l,m,x);
        else update(2*i+1,m+1,r,x);
        st[i]=st[2*i]+st[2*i+1];
    }
}
int gsum(int i,int l,int r,int tl,int tr)
{
    if(l>r||tl>r||l>tr)return 0;
    if(tl<=l&&r<=tr)return st[i];
    int m=(l+r)/2;
    return gsum(2*i,l,m,tl,tr)+gsum(2*i+1,m+1,r,tl,tr);
}
vector<int> check_validity(int n,vector<int> x,vector<int> y,vector<int> S,vector<int> E,vector<int> L,vector<int> R)
{
    int m=x.size(),q=L.size();
    vector<int>pos(n),res(q);
    krt a(n),b(n);
    st.resize(4*n+1);
    vector<vector<int>>koce(n);
    vector<vector<pair<int,pair<int,int>>>>lq(n),rq(n);
    for(int i=0;i<m;i++)
    {
        if(x[i]<y[i])swap(x[i],y[i]);
        koce[x[i]].push_back(y[i]);
    }
    for(int i=0;i<n;i++)
    {
        for(auto j:koce[i])
        {
            a.kmerge(i,j,1);
        }
        koce[i].clear();
    }
    a.dfs(n-1,n-1);
    for(int i=0;i<m;i++)
    {
        koce[y[i]].push_back(x[i]);
    }
    for(int i=n-1;i>=0;i--)
    {
        for(auto j:koce[i])
        {
            b.kmerge(i,j,0);
        }
    }
    b.dfs(0,0);
    for(int i=0;i<n;i++)pos[a.el[i]]=b.el[i];
    for(int i=0;i<q;i++)
    {
        int s=S[i],e=E[i],l=L[i],r=R[i];
        for(int j=19;j>=0;j--)
        {
            if(b.lca[s][j]>=l)s=b.lca[s][j];
            if(a.lca[e][j]<=r)e=a.lca[e][j];
        }
        lq[a.el[e]].push_back({i,{b.el[s],b.er[s]}});
        rq[a.er[e]].push_back({i,{b.el[s],b.er[s]}});
    }
    for(int i=0;i<n;i++)
    {
        for(auto p:lq[i])
        {
            res[p.first]-=gsum(1,0,n-1,p.second.first,p.second.second);
        }
        update(1,0,n-1,pos[i]);
        for(auto p:rq[i])
        {
            res[p.first]+=gsum(1,0,n-1,p.second.first,p.second.second);
        }
    }
    for(int i=0;i<q;i++)
    {
        if(res[i]>0)res[i]=1;
        else res[i]=0;
    }
    return res;
}

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