Submission #435809

#	Time	Username	Problem	Language	Result	Execution time	Memory
435809		MOUF_MAHMALAT	Werewolf (IOI18_werewolf)	C++14	0 / 100	945 ms	102428 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define F first
#define S second
using namespace std;
typedef int ll;
typedef pair<ll,ll>pll;
ll n,k,p[400009],nn,is;
ll dp1[400009][20],dp2[400009][20];
ll h1[400009],h2[400009];
ll f1[400009],f2[400009];
vector<pll>op;
vector<vector<ll> >v;
vector<ll>ans;
ll gp(ll z)
{
    if(p[z]==z)
        return z;
    return p[z]=gp(p[z]);
}
void mrg(ll x,ll y)
{
    x=gp(x),y=gp(y);
    if(x==y)
        return;
    nn++;
    p[x]=p[y]=p[nn]=nn;
    v[nn].push_back(x);
    v[nn].push_back(y);
    if(is==1)
        f1[nn]=min(f1[x],f1[y]);
    else
        f2[nn]=max(f2[x],f2[y]);
}
bool cmp1(const pll&x,const pll&y)
{
    return min(x.F,x.S)>min(y.F,y.S);
}
bool cmp2(const pll&x,const pll&y)
{
    return max(x.F,x.S)<max(y.F,y.S);
}
void dfs(ll d,ll p)
{
    if(is==1)
        dp1[d][0]=p,h1[d]=h1[p]+1;
    else
        dp2[d][0]=p,h2[d]=h2[p]+1;
    for(auto z:v[d])
        if(z!=p)
            dfs(z,d);
}
ll lca1(ll x,ll y)
{
    if(h1[x]<h1[y])
        swap(x,y);
    ll j=h1[x]-h1[y];
    for(ll i=0; i<=k; i++)
        if((1<<i)&j)
            x=dp1[x][i];
    for(ll i=k; i>=0; i--)
        if(dp1[x][i]!=dp1[y][i])
            x=dp1[x][i],y=dp1[y][i];
    if(x==y)
        return x;
    return dp1[x][0];
}
ll lca2(ll x,ll y)
{
    if(h2[x]<h2[y])
        swap(x,y);
    ll j=h2[x]-h2[y];
    for(ll i=0; i<=k; i++)
        if((1<<i)&j)
            x=dp2[x][i];
    for(ll i=k; i>=0; i--)
        if(dp2[x][i]!=dp2[y][i])
            x=dp2[x][i],y=dp2[y][i];
    if(x==y)
        return x;
    return dp1[x][0];
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                           vector<int> st, vector<int> en,
                           vector<int> L, vector<int> R)
{
    n=N;
    for(ll i=0; i<X.size(); i++)
        op.push_back({X[i],Y[i]});
    for(ll i=0; i<n; i++)
        p[i]=f1[i]=i;
    sort(all(op),cmp1),nn=n-1,is=1;
    v.resize(2*n);
    for(auto z:op)
        mrg(z.F,z.S);
    dfs(nn,nn);

    for(ll i=0; i<n; i++)
        p[i]=f2[i]=i;
    sort(all(op),cmp2),nn=n-1,is=2;
    v.clear(),v.resize(2*n);
    for(auto z:op)
        mrg(z.F,z.S);
    dfs(nn,nn);
    k=log2(nn)+1;
    for(ll j=1; j<=k; j++)
        for(ll i=0; i<=nn; i++)
        {
            dp1[i][j]=dp1[ dp1[i][j-1] ][j-1];
            dp2[i][j]=dp2[ dp2[i][j-1] ][j-1];
        }
    ans.resize(L.size());
    for(ll i=0; i<L.size(); i++)
    {
        ll x=st[i],y=en[i];
        if(f1[lca1(x,y)]>=L[i])
            ans[i]=1;
        if(f2[lca2(x,y)]<=R[i])
            ans[i]=1;
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:89:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(ll i=0; i<X.size(); i++)
      |                 ~^~~~~~~~~
werewolf.cpp:114:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(ll i=0; i<L.size(); i++)
      |                 ~^~~~~~~~~

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