Submission #718755

#	Time	Username	Problem	Language	Result	Execution time	Memory
718755		ogibogi2004	Werewolf (IOI18_werewolf)	C++14	0 / 100	1294 ms	366184 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+6;
const int logN=18;
struct node
{
    int left_child,right_child,maxval;
};
vector<node>nodes;
vector<int>g[MAXN];
int in_time[MAXN][2];
int out_time[MAXN][2];
int par[2][MAXN][logN];
int x[MAXN],y[MAXN];
struct tree_2d
{
    set<int>s[3*MAXN];
    void build(int l,int r,int idx)
    {
        for(int i=l;i<=r;i++)s[idx].insert(y[i]);
        if(l==r)return;
        int mid=(l+r)/2;

        build(l,mid,idx*2);
        build(mid+1,r,idx*2+1);
    }
    bool query(int l,int r,int idx,int ql,int qr,int ql1,int qr1)
    {
        if(l>qr)return 0;
        if(r<ql)return 0;
        if(l>=ql&&r<=qr)
        {
            auto it=s[idx].lower_bound(ql1);
            if(it!=s[idx].end()&&(*it)<=qr1)return 1;
            return 0;
        }
        int mid=(l+r)/2;
        return query(l,mid,idx*2,ql,qr,ql1,qr1)||query(mid+1,r,idx*2+1,ql,qr,ql1,qr1);
    }
}tr;
struct dsu
{
    int par[2*MAXN];
    void init()
    {
        for(int i=0;i<MAXN;i++)
        {
            par[i]=i;
        }
    }
    int getRoot(int u)
    {
        if(u==par[u])return u;
        return par[u]=getRoot(par[u]);
    }
    void join(int p,int q,int f)
    {
        p=getRoot(p);
        q=getRoot(q);
        if(p==q)return;
        int t=nodes.size();
        par[p]=t;par[q]=t;
        if(!f)nodes.push_back({p,q,max(nodes[p].maxval,nodes[q].maxval)});
        else nodes.push_back({p,q,min(nodes[p].maxval,nodes[q].maxval)});
    }
}dsu1;
int t,n;
void dfs(int u,int p,int f)
{
    in_time[u][f]=++t;
    par[f][u][0]=p;
    if(nodes[u].left_child!=-1)dfs(nodes[u].left_child,u,f);
    if(nodes[u].right_child!=-1)dfs(nodes[u].right_child,u,f);
    out_time[u][f]=t;
}
void precompute()
{
    for(int f=0;f<1;f++)
    for(int step=1;step<logN;step++)
    {
        for(int i=0;i<n;i++)
        {
            if(par[f][i][step-1]==-1)par[f][i][step]=-1;
            else par[f][i][step]=par[f][par[f][i][step-1]][step-1];
        }
    }
}
int lift_left(int vert,int l)
{
    if(vert<l)return -1;
    for(int j=logN-1;j>=0;j--)
    {
        if(par[0][vert][j]==-1)continue;
        if(nodes[par[0][vert][j]].maxval<l)continue;
        vert=par[0][vert][j];
    }
    return vert;
}
int lift_right(int vert,int r)
{
    if(vert>r)return -1;
    for(int j=logN-1;j>=0;j--)
    {
        if(par[1][vert][j]==-1)continue;
        if(nodes[par[1][vert][j]].maxval>r)continue;
        vert=par[1][vert][j];
    }
    return vert;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {

        n=N;
        for(int i=0;i<X.size();i++)
        {
            g[X[i]].push_back(Y[i]);
            g[Y[i]].push_back(X[i]);
        }
        for(int i=0;i<N;i++)
        {
            nodes.push_back({-1,-1,i});
        }
        //cout<<"*0\n";
        dsu1.init();
        for(int i=N-1;i>=0;i--)
        {
            //cout<<"%% "<<i<<endl;
            for(auto xd:g[i])
            {
                if(xd>i)
                {
                    dsu1.join(xd,i,0);
                }
            }
        }
        t=0;
        //cout<<"*0.5\n";
        dfs(nodes.size()-1,-1,0);
        //cout<<"*1\n";
        nodes.clear();
        for(int i=0;i<N;i++)
        {
            nodes.push_back({-1,-1,i});
        }
        dsu1.init();
        for(int i=0;i<N;i++)
        {
            for(auto xd:g[i])
            {
                if(xd<i)
                {
                    dsu1.join(xd,i,1);
                }
            }
        }
        t=0;
        dfs(nodes.size()-1,-1,1);

        precompute();

        //cout<<"*2\n";
        for(int i=0;i<N;i++)
        {
            x[i]=in_time[i][0];
            y[i]=in_time[i][1];
            //cout<<x[i]<<" "<<y[i]<<endl;
        }
        tr.build(1,nodes.size(),1);
        vector<int>ans;
        //cout<<"*3\n";
        for(int i=0;i<L.size();i++)
        {
            int t1=lift_left(S[i],L[i]);
            int t2=lift_right(E[i],R[i]);
            if(t1!=-1&&t2!=-1&&tr.query(1,nodes.size(),1,in_time[t1][0], out_time[t1][0],in_time[t2][1],out_time[t2][1]))
            {
                ans.push_back(1);
            }
            else ans.push_back(0);
        }
        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:116:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for(int i=0;i<X.size();i++)
      |                     ~^~~~~~~~~
werewolf.cpp:173:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |         for(int i=0;i<L.size();i++)
      |                     ~^~~~~~~~~

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