Submission #284343

#	Time	Username	Problem	Language	Result	Execution time	Memory
284343		MKopchev	Werewolf (IOI18_werewolf)	C++14	0 / 100	4078 ms	80368 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];

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<N&&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;
    }

    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<N&&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)]};
        }
    }

    vector<int> ret={};

    for(int i=0;i<L.size();i++)
    {
        int cur=0;

        set<int> help={};

        for(int j=mem_mini[i].first;j<=mem_mini[i].second;j++)
            help.insert(order_mini[j]);

        for(int j=mem_maxi[i].first;j<=mem_maxi[i].second&&cur==0;j++)
            if(help.count(order_maxi[j]))
                cur=1;

        ret.push_back(cur);
    }

    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:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i=0;i<L.size();i++)
      |                 ~^~~~~~~~~
werewolf.cpp:152:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for(int i=0;i<R.size();i++)
      |                 ~^~~~~~~~~
werewolf.cpp:177:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for(int i=0;i<L.size();i++)
      |                 ~^~~~~~~~~

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