Submission #824910

#	Time	Username	Problem	Language	Result	Execution time	Memory
824910		andrei_boaca	Fountain Parks (IOI21_parks)	C++17	70 / 100	3583 ms	136828 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;

typedef pair<int,int> pii;
map<pii,int> ind;
map<pii,int> ocup;
map<pii,int> match;
struct point
{
    int x,y;
} v[200005];
int k;
vector<int> myy[200005];
vector<int> muchii[200005];
vector<pii> edges;
bool have[11][200005];
bool use[200005];
void dfs(int nod)
{
    use[nod]=1;
    for(int i:muchii[nod])
        if(!use[i])
            dfs(i);
}
int c[11][200005];
vector<int> U,V,A,B;
void addedge(int xa,int ya,int xb,int yb,int xc,int yc)
{
    int a=ind[{xa,ya}];
    int b=ind[{xb,yb}];
    U.push_back(a);
    V.push_back(b);
    muchii[a].push_back(b);
    muchii[b].push_back(a);
    A.push_back(xc);
    B.push_back(yc);
}
int diri[5]={-2,2,0,0};
int dirj[5]={0,0,-2,2};
int nr;
vector<int> cedge[800005];
int l[800005],r[800005];
vector<pii> who;
bool pairup(int nod)
{
    if(use[nod])
        return 0;
    use[nod]=1;
    for(int i:cedge[nod])
        if(r[i]==0)
        {
            l[nod]=i;
            r[i]=nod;
            return 1;
        }
    for(int i:cedge[nod])
        if(pairup(r[i]))
        {
            l[nod]=i;
            r[i]=nod;
            return 1;
        }
    return 0;
}
int comp[700005];
vector<int> dsu[700005];
void dsu_merge(int c1,int c2)
{
    if(dsu[c1].size()<dsu[c2].size())
        swap(c1,c2);
    for(int i:dsu[c2])
    {
        comp[i]=c1;
        dsu[c1].push_back(i);
    }
    dsu[c2].clear();
}
int construct_roads(std::vector<int> X, std::vector<int> Y)
{
    k=X.size();
    int xmax=0;
    for(int i=0;i<k;i++)
    {
        v[i]={X[i],Y[i]};
        ind[{X[i],Y[i]}]=i;
        xmax=max(xmax,X[i]);
        if(X[i]<=6)
        {
            myy[X[i]].push_back(Y[i]);
            have[X[i]][Y[i]]=1;
        }
    }
    if(xmax<=2)
    {
        sort(myy[2].begin(),myy[2].end());
        vector<int> U,V,a,b;
        for(int i=1;i<myy[2].size();i++)
        {
            if(myy[2][i]-myy[2][i-1]!=2)
                return 0;
            int x=2;
            int yu=myy[2][i-1];
            int yv=myy[2][i];
            U.push_back(ind[{x,yu}]);
            V.push_back(ind[{x,yv}]);
            a.push_back(x-1);
            b.push_back(yv-1);
        }
        build(U,V,a,b);
        return 1;
    }
    if(xmax<=4)
    {
        sort(myy[2].begin(),myy[2].end());
        sort(myy[4].begin(),myy[4].end());
        vector<int> U,V,A,B;
        for(int i=2;i<=200000;i+=2)
            if(have[2][i]&&have[2][i-2])
            {
                int a=ind[{2,i}];
                int b=ind[{2,i-2}];
                U.push_back(a);
                V.push_back(b);
                muchii[a].push_back(b);
                muchii[b].push_back(a);
                A.push_back(1);
                B.push_back(i-1);
            }
        for(int i=2;i<=200000;i+=2)
            if(have[4][i]&&have[4][i-2])
            {
                int a=ind[{4,i}];
                int b=ind[{4,i-2}];
                U.push_back(a);
                V.push_back(b);
                muchii[a].push_back(b);
                muchii[b].push_back(a);
                A.push_back(5);
                B.push_back(i-1);
            }
        for(int i=2;i<=200000;i+=2)
            if(have[2][i]&&have[4][i])
            {
                int a=ind[{2,i}];
                int b=ind[{4,i}];
                U.push_back(a);
                V.push_back(b);
                muchii[a].push_back(b);
                muchii[b].push_back(a);
                A.push_back(3);
                B.push_back(i+1);
            }
        dfs(0);
        for(int i=0;i<k;i++)
            if(!use[i])
                return 0;
        build(U,V,A,B);
        return 1;
    }
    if(xmax<=6)
    {
        sort(myy[2].begin(),myy[2].end());
        sort(myy[4].begin(),myy[4].end());
        sort(myy[6].begin(),myy[6].end());
        int nr=0;
        for(int i=2;i<=200000;i+=2)
            if(have[2][i])
            {
                if(have[2][i-2])
                {
                    addedge(2,i,2,i-2,1,i-1);
                    c[2][i]=c[2][i-2];
                }
                else
                {
                    nr++;
                    c[2][i]=nr;
                }
            }
        for(int i=2;i<=200000;i+=2)
            if(have[6][i])
            {
                if(have[6][i-2])
                {
                    addedge(6,i,6,i-2,7,i-1);
                    c[6][i]=c[6][i-2];
                }
                else
                {
                    nr++;
                    c[6][i]=nr;
                }
            }
        int lft=1;
        for(int i=2;i<=200000;i+=2)
            if(have[4][i])
            {
                if(have[4][i-2])
                {
                    if(lft==1)
                    {
                        addedge(4,i,4,i-2,3,i-1);
                        ocup[{3,i-1}]=1;
                    }
                    else
                    {
                        addedge(4,i,4,i-2,5,i-1);
                        ocup[{5,i-1}]=1;
                    }
                    lft^=1;
                    c[4][i]=c[4][i-2];
                }
                else
                {
                    lft=1;
                    nr++;
                    c[4][i]=nr;
                }
            }
        for(int i=2;i<=200000;i+=2)
            if(have[2][i]&&have[4][i])
            {
                int a=c[2][i];
                int b=c[4][i];
                if(match[{a,b}]==0)
                    {
                        match[{a,b}]=1;
                        if(!ocup[{3,i-1}])
                            {
                                addedge(2,i,4,i,3,i-1);
                                ocup[{3,i-1}]=1;
                            }
                        else
                        {
                            addedge(2,i,4,i,3,i+1);
                            ocup[{3,i+1}]=1;
                        }
                    }
            }
        for(int i=2;i<=200000;i+=2)
            if(have[4][i]&&have[6][i])
            {
                int a=c[4][i];
                int b=c[6][i];
                if(match[{a,b}]==0)
                    {
                        match[{a,b}]=1;
                        if(!ocup[{5,i-1}])
                            {
                                addedge(4,i,6,i,5,i-1);
                                ocup[{5,i-1}]=1;
                            }
                        else
                        {
                            addedge(4,i,6,i,5,i+1);
                            ocup[{5,i+1}]=1;
                        }
                    }
            }
        dfs(0);
        for(int i=0;i<k;i++)
            if(!use[i])
                return 0;
        build(U,V,A,B);
        return 1;
    }
    vector<int> nodes;
    for(int i=0;i<k;i++)
        nodes.push_back(i);
    int bulan=0;
    nr=0;
    while(bulan<=5)
    {
        random_shuffle(nodes.begin(),nodes.end());
        bulan++;
        bool good=1;
        for(int i=0;i<k;i++)
        {
            comp[i]=i;
            dsu[i].clear();
            dsu[i].push_back(i);
            muchii[i].clear();
            use[i]=0;
        }
        edges.clear();
        for(auto p:nodes)
        {
            int nod=p;
            int x=X[nod];
            int y=Y[nod];
            for(int z=0;z<4;z++)
            {
                int lin=x+diri[z];
                int col=y+dirj[z];
                if(ind.count({lin,col})!=0)
                    {
                        int w=ind[{lin,col}];
                        if(comp[nod]!=comp[w])
                        {
                            dsu_merge(comp[nod],comp[w]);
                            muchii[nod].push_back(w);
                            muchii[w].push_back(nod);
                            edges.push_back({nod,w});
                        }
                    }
            }
        }
        dfs(0);
        for(int i=0;i<k;i++)
            if(!use[i])
                good=0;
        if(good==0)
            continue;
        who.clear();
        who.push_back({0,0});
        for(int i=0;i<edges.size();i++)
        {
            cedge[i+1].clear();
            int a=edges[i].first;
            int b=edges[i].second;
            int xa=X[a],ya=Y[a],xb=X[b],yb=Y[b];
            if(xa==xb)
            {
                int x=xa+1;
                int y=(ya+yb)/2;
                if(ind[{x,y}]==0)
                    {
                        nr++;
                        ind[{x,y}]=nr;
                        who.push_back({x,y});
                    }
                int nrm=ind[{x,y}];
                cedge[i+1].push_back(nrm);

                x=xa-1;
                y=(ya+yb)/2;
                if(ind[{x,y}]==0)
                    {
                        nr++;
                        ind[{x,y}]=nr;
                        who.push_back({x,y});
                    }
                nrm=ind[{x,y}];
                cedge[i+1].push_back(nrm);
            }
            else
            {
                int x=(xa+xb)/2;
                int y=ya-1;
                if(ind[{x,y}]==0)
                    {
                        nr++;
                        ind[{x,y}]=nr;
                        who.push_back({x,y});
                    }
                int nrm=ind[{x,y}];
                cedge[i+1].push_back(nrm);

                x=(xa+xb)/2;
                y=ya+1;
                if(ind[{x,y}]==0)
                    {
                        nr++;
                        ind[{x,y}]=nr;
                        who.push_back({x,y});
                    }
                nrm=ind[{x,y}];
                cedge[i+1].push_back(nrm);
            }
        }
        for(int i=1;i<=edges.size();i++)
            l[i]=0;
        for(int i=1;i<=nr;i++)
            r[i]=0;
        bool ok=0;
        do
        {
            ok=0;
            for(int i=1;i<=edges.size();i++)
                use[i]=0;
            for(int i=1;i<=edges.size();i++)
                if(l[i]==0)
                    ok|=pairup(i);
        }while(ok);
        for(int i=1;i<=edges.size();i++)
            if(l[i]==0)
                good=0;
        if(good==0)
            continue;
        for(int i=1;i<=edges.size();i++)
        {
            U.push_back(edges[i-1].first);
            V.push_back(edges[i-1].second);
            A.push_back(who[l[i]].first);
            B.push_back(who[l[i]].second);
        }
        build(U,V,A,B);
        return 1;
    }
    return 0;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int i=1;i<myy[2].size();i++)
      |                     ~^~~~~~~~~~~~~~
parks.cpp:318:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  318 |         for(int i=0;i<edges.size();i++)
      |                     ~^~~~~~~~~~~~~
parks.cpp:373:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  373 |         for(int i=1;i<=edges.size();i++)
      |                     ~^~~~~~~~~~~~~~
parks.cpp:381:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  381 |             for(int i=1;i<=edges.size();i++)
      |                         ~^~~~~~~~~~~~~~
parks.cpp:383:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  383 |             for(int i=1;i<=edges.size();i++)
      |                         ~^~~~~~~~~~~~~~
parks.cpp:387:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  387 |         for(int i=1;i<=edges.size();i++)
      |                     ~^~~~~~~~~~~~~~
parks.cpp:392:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  392 |         for(int i=1;i<=edges.size();i++)
      |                     ~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30