Submission #284366

#	Time	Username	Problem	Language	Result	Execution time	Memory
284366		MKopchev	Werewolf (IOI18_werewolf)	C++14	100 / 100	807 ms	84324 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=4e5+42;

struct edge
{
    int u,v,cost;
};
edge all[nmax];

bool cmp_1(edge a,edge b)
{
    return a.cost<b.cost;
}

bool cmp_2(edge a,edge b)
{
    return a.cost>b.cost;
}

int parent[nmax];

int root(int node)
{
    if(parent[node]==node)return node;
    parent[node]=root(parent[node]);
    return parent[node];
}

vector<int> seen[nmax];

int le[nmax],ri[nmax];

void my_merge(int u,int v)
{
    u=root(u);
    v=root(v);

    if(u==v)return;

    //cout<<"my_merge "<<u<<" "<<v<<endl;

    if(seen[u].size()<seen[v].size())swap(u,v);

    for(auto k:seen[v])
        seen[u].push_back(k);

    le[u]=min(le[u],le[v]);
    ri[u]=max(ri[u],ri[v]);

    parent[v]=u;
}

int order_mini[nmax],order_maxi[nmax];

vector< pair<int,int> > queries[nmax];

pair<int,int> mem_mini[nmax],mem_maxi[nmax];


int where[nmax];

pair<int,int> points[nmax];

struct rect
{
    int x1,y1,x2,y2,id;
};
rect help[nmax];

bool cmp_rect(rect a,rect b)
{
    return a.x2<b.x2;
}

int tree[4*nmax];

void update(int node,int l,int r,int pos,int val)
{
    tree[node]=max(tree[node],val);

    if(l==r)return;

    int av=(l+r)/2;

    if(pos<=av)update(node*2,l,av,pos,val);
    else update(node*2+1,av+1,r,pos,val);
}

int query(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return tree[node];

    int av=(l+r)/2,ret=-1;

    if(lq<=av)ret=max(ret,query(node*2,l,av,lq,min(av,rq)));
    if(av<rq)ret=max(ret,query(node*2+1,av+1,r,max(av+1,lq),rq));

    return ret;
}
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)
{
        int M=X.size();
    //min tree

    for(int i=0;i<M;i++)
    {
        all[i].u=X[i];
        all[i].v=Y[i];
        all[i].cost=max(X[i],Y[i]);
    }

    for(int i=0;i<N;i++)parent[i]=i;

    sort(all,all+M,cmp_1);

    for(int i=0;i<N;i++)seen[i]={i};

    for(int i=0;i<M;i++)
    {
        my_merge(all[i].u,all[i].v);
        /*
        for(int j=0;j<N;j++)
        {
            cout<<j<<" -> "<<root(j)<<" : ";for(auto k:seen[j])cout<<k<<" ";cout<<endl;
        }
        */
    }


    for(int i=0;i<N;i++)
    {
        order_mini[i]=seen[root(0)][i];
        le[order_mini[i]]=i;
        ri[order_mini[i]]=i;

        //cout<<i<<" -> "<<order_mini[i]<<endl;
    }

    for(int i=0;i<L.size();i++)
        queries[R[i]].push_back({E[i],i});

    for(int i=0;i<N;i++)parent[i]=i;

    for(int i=0;i<N;i++)seen[i]={};

    int pointer=0;
    for(int t=0;t<N;t++)
    {
        while(pointer<M&&all[pointer].cost==t)
        {
            my_merge(all[pointer].u,all[pointer].v);
            pointer++;
        }

        for(auto k:queries[t])
        {
            mem_mini[k.second]={le[root(k.first)],ri[root(k.first)]};
        }
    }

    //max tree
    for(int i=0;i<M;i++)
    {
        all[i].u=X[i];
        all[i].v=Y[i];
        all[i].cost=min(X[i],Y[i]);
    }

    for(int i=0;i<N;i++)parent[i]=i;

    sort(all,all+M,cmp_2);

    for(int i=0;i<N;i++)seen[i]={i};

    for(int i=0;i<M;i++)
        my_merge(all[i].u,all[i].v);

    for(int i=0;i<N;i++)
    {
        order_maxi[i]=seen[root(0)][i];
        le[order_maxi[i]]=i;
        ri[order_maxi[i]]=i;

        //cout<<i<<" -> "<<order_maxi[i]<<endl;
    }

    for(int i=0;i<N;i++)
        queries[i]={};

    for(int i=0;i<R.size();i++)
        queries[L[i]].push_back({S[i],i});

    for(int i=0;i<N;i++)parent[i]=i;

    for(int i=0;i<N;i++)seen[i]={};

    pointer=0;

    for(int t=N-1;t>=0;t--)
    {
        while(pointer<M&&all[pointer].cost==t)
        {
            my_merge(all[pointer].u,all[pointer].v);
            pointer++;
        }

        for(auto k:queries[t])
        {
            mem_maxi[k.second]={le[root(k.first)],ri[root(k.first)]};
        }
    }

    for(int i=0;i<N;i++)
    {
        where[order_mini[i]]=i;
    }

    for(int i=0;i<N;i++)
    {
        points[i]={where[order_maxi[i]],i};

        //cout<<points[i].first<<" "<<points[i].second<<endl;
    }

    sort(points,points+N);

    for(int i=0;i<L.size();i++)
    {
        help[i].x1=mem_mini[i].first;
        help[i].x2=mem_mini[i].second;

        help[i].y1=mem_maxi[i].first;
        help[i].y2=mem_maxi[i].second;

        //cout<<i<<" -> "<<help[i].x1<<" "<<help[i].y1<<" "<<help[i].x2<<" "<<help[i].y2<<endl;

        help[i].id=i;
    }

    sort(help,help+L.size(),cmp_rect);

    memset(tree,-1,sizeof(tree));

    vector<int> ret(L.size(),0);

    int pointer_points=0,pointer_queries=0;

    for(int x=0;x<N;x++)
    {

        while(pointer_points<N&&points[pointer_points].first==x)
        {
            update(1,0,N-1,points[pointer_points].second,points[pointer_points].first);

            //cout<<"update "<<points[pointer_points].second<<" with "<<points[pointer_points].first<<endl;

            pointer_points++;
        }

        //for(int j=0;j<N;j++)cout<<j<<" -> "<<query(1,0,N-1,j,j)<<endl;

        while(pointer_queries<L.size()&&help[pointer_queries].x2==x)
        {
            ret[help[pointer_queries].id]=(query(1,0,N-1,help[pointer_queries].y1,help[pointer_queries].y2)>=help[pointer_queries].x1);

            //cout<<query(1,0,N-1,help[pointer_queries].y1,help[pointer_queries].y2)<<" wanted "<<help[pointer_queries].x1<<endl;

            pointer_queries++;
        }

        //cout<<"---"<<endl;
    }

    return ret;
}

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:144:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for(int i=0;i<L.size();i++)
      |                 ~^~~~~~~~~
werewolf.cpp:195:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |     for(int i=0;i<R.size();i++)
      |                 ~^~~~~~~~~
werewolf.cpp:232:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  232 |     for(int i=0;i<L.size();i++)
      |                 ~^~~~~~~~~
werewolf.cpp:267:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  267 |         while(pointer_queries<L.size()&&help[pointer_queries].x2==x)
      |               ~~~~~~~~~~~~~~~^~~~~~~~~

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