Submission #441458

# Submission time Handle Problem Language Result Execution time Memory
441458 2021-07-05T08:24:55 Z daniel920712 Distributing Candies (IOI21_candies) C++17
Compilation error
0 ms 0 KB
#include "parks.h"
#include <map>
#include <utility>
#include <queue>
#include <set>
using namespace std;
map < pair < int , int > , int > all,con;
map < pair < int , int > , pair < int , int > > road;
vector < int > u,v,a,b;
queue < pair < int , int > > BFS;
set < pair < int , int > > still,Not,have;
int Father[200005];
int Find(int here)
{
    if(Father[here]==here) return here;
    Father[here]=Find(Father[here]);
    return Father[here];
}
int construct_roads(vector < int > x, vector < int > y)
{
    int N=x.size(),M,i,t,aa,bb,ok=1,xx,yy,big=0;
    for(i=0;i<N;i++)
    {
        all[make_pair(x[i],y[i])]=i;
        Father[i]=i;
        big=max(big,x[i]);
    }
    if(big<=6)
    {
        for(i=0;i<N;i++)
        {
            if(all.find(make_pair(x[i],y[i]+2))!=all.end())
            {
                t=all[make_pair(x[i],y[i]+2)];
                aa=Find(i);
                bb=Find(t);
                if(aa!=bb) Father[aa]=bb;
                if(x[i]==2)
                {
                    u.push_back(i);
                    v.push_back(t);
                    a.push_back(x[i]-1);
                    b.push_back(y[i]+1);
                }
                else if(x[i]==4)
                {
                    if(y[i]%4==0)
                    {
                        u.push_back(i);
                        v.push_back(t);
                        a.push_back(x[i]-1);
                        b.push_back(y[i]+1);
                    }
                    else
                    {
                        u.push_back(i);
                        v.push_back(t);
                        a.push_back(x[i]+1);
                        b.push_back(y[i]+1);
                    }
                }
                else if(x[i]==6)
                {
                    u.push_back(i);
                    v.push_back(t);
                    a.push_back(x[i]+1);
                    b.push_back(y[i]+1);
                }

            }
            if(all.find(make_pair(x[i]+2,y[i]))!=all.end())
            {
                t=all[make_pair(x[i]+2,y[i])];
                aa=Find(i);
                bb=Find(t);
                if(aa!=bb) Father[aa]=bb;
                if(y[i]%4==0)
                {
                    if(x[i]==2)
                    {
                        u.push_back(i);
                        v.push_back(t);
                        a.push_back(x[i]+1);
                        b.push_back(y[i]-1);
                    }
                    else
                    {
                        u.push_back(i);
                        v.push_back(t);
                        a.push_back(x[i]+1);
                        b.push_back(y[i]+1);
                    }
                }
                else
                {
                    Not.insert(make_pair(i,t));
                }
            }
        }
        M=a.size();
        for(i=0;i<M;i++) have.insert(make_pair(a[i],b[i]));
        for(auto i:Not)
        {
            if(have.find(make_pair(x[i.first]+1,y[i.first]+1))==have.end())
            {
                have.insert(make_pair(x[i.first]+1,y[i.first]+1));
                u.push_back(i.first);
                v.push_back(i.second);
                a.push_back(x[i.first]+1);
                b.push_back(y[i.first]+1);
            }
            else if(have.find(make_pair(x[i.first]+1,y[i.first]-1))==have.end())
            {
                have.insert(make_pair(x[i.first]+1,y[i.first]-1));
                u.push_back(i.first);
                v.push_back(i.second);
                a.push_back(x[i.first]+1);
                b.push_back(y[i.first]-1);
            }
        }
        t=Find(0);
        for(i=0;i<N;i++)
        {

            if(t!=Find(i)) ok=0;
        }
        if(ok==0) return ok;



        if(ok) build(u,v,a,b);
        return ok;
    }
    else
    {
        for(i=0;i<N;i++)
        {
            if(all.find(make_pair(x[i],y[i]+2))!=all.end())
            {
                t=all[make_pair(x[i],y[i]+2)];
                road[make_pair(x[i],y[i]+1)]=make_pair(i,t);
                con[make_pair(x[i]+1,y[i]+1)]++;
                con[make_pair(x[i]-1,y[i]+1)]++;

                aa=Find(i);
                bb=Find(t);
                if(aa!=bb) Father[aa]=bb;

            }
            if(all.find(make_pair(x[i]+2,y[i]))!=all.end())
            {
                t=all[make_pair(x[i]+2,y[i])];
                road[make_pair(x[i]+1,y[i])]=make_pair(i,t);
                con[make_pair(x[i]+1,y[i]+1)]++;
                con[make_pair(x[i]+1,y[i]-1)]++;
                aa=Find(i);
                bb=Find(t);
                if(aa!=bb) Father[aa]=bb;
            }
        }
        t=Find(0);
        for(i=0;i<N;i++)  if(t!=Find(i)) ok=0;
        if(ok==0) return ok;
        for(auto i:con)
        {
            still.insert(i.first);
            if(i.second==1) BFS.push(i.first);
        }
        while(!BFS.empty())
        {
            xx=BFS.front().first;
            yy=BFS.front().second;
            BFS.pop();
            still.erase(make_pair(xx,yy));
            if(con[make_pair(xx,yy)]<=0) continue;
            if(road.find(make_pair(xx+1,yy))!=road.end()) aa=xx+1,bb=yy;
            if(road.find(make_pair(xx-1,yy))!=road.end()) aa=xx-1,bb=yy;
            if(road.find(make_pair(xx,yy+1))!=road.end()) aa=xx,bb=yy+1;
            if(road.find(make_pair(xx,yy-1))!=road.end()) aa=xx,bb=yy-1;
            u.push_back(road[make_pair(aa,bb)].first);
            v.push_back(road[make_pair(aa,bb)].second);
            a.push_back(xx);
            b.push_back(yy);
            road.erase(make_pair(aa,bb));
            con[make_pair(xx,yy)]=0;

            if(aa%2==0)
            {
                con[make_pair(aa-1,bb)]--;
                con[make_pair(aa+1,bb)]--;

                if(con[make_pair(aa-1,bb)]==1) BFS.push(make_pair(aa-1,bb));
                if(con[make_pair(aa+1,bb)]==1) BFS.push(make_pair(aa+1,bb));
            }
            else
            {
                con[make_pair(aa,bb-1)]--;
                con[make_pair(aa,bb+1)]--;

                if(con[make_pair(aa,bb-1)]==1) BFS.push(make_pair(aa,bb-1));
                if(con[make_pair(aa,bb+1)]==1) BFS.push(make_pair(aa,bb+1));
            }

        }
        while(!still.empty())
        {
            BFS.push(*still.begin());
            while(!BFS.empty())
            {
                ok=0;
                xx=BFS.front().first;
                yy=BFS.front().second;
                BFS.pop();
                still.erase(make_pair(xx,yy));
                if(con[make_pair(xx,yy)]<=0) continue;
                if(road.find(make_pair(xx+1,yy))!=road.end()) aa=xx+1,bb=yy,ok=1;
                if(road.find(make_pair(xx-1,yy))!=road.end()) aa=xx-1,bb=yy,ok=1;
                if(road.find(make_pair(xx,yy+1))!=road.end()) aa=xx,bb=yy+1,ok=1;
                if(road.find(make_pair(xx,yy-1))!=road.end()) aa=xx,bb=yy-1,ok=1;
                con[make_pair(xx,yy)]=0;

                if(ok==0) continue;
                u.push_back(road[make_pair(aa,bb)].first);
                v.push_back(road[make_pair(aa,bb)].second);
                a.push_back(xx);
                b.push_back(yy);
                road.erase(make_pair(aa,bb));

                if(aa%2==0)
                {
                    con[make_pair(aa-1,bb)]--;
                    con[make_pair(aa+1,bb)]--;

                    if(con[make_pair(aa-1,bb)]==1) BFS.push(make_pair(aa-1,bb));
                    if(con[make_pair(aa+1,bb)]==1) BFS.push(make_pair(aa+1,bb));
                }
                else
                {
                    con[make_pair(aa,bb-1)]--;
                    con[make_pair(aa,bb+1)]--;

                    if(con[make_pair(aa,bb-1)]==1) BFS.push(make_pair(aa,bb-1));
                    if(con[make_pair(aa,bb+1)]==1) BFS.push(make_pair(aa,bb+1));
                }

            }
        }
        if(!road.empty()) return 0;


        if(ok) build(u,v,a,b);
        return ok;
    }

}

Compilation message

candies.cpp:1:10: fatal error: parks.h: No such file or directory
    1 | #include "parks.h"
      |          ^~~~~~~~~
compilation terminated.