Submission #623184

#	Time	Username	Problem	Language	Result	Execution time	Memory
623184		Hanksburger	Fountain Parks (IOI21_parks)	C++17	30 / 100	359 ms	60840 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > vec[200005], edge;
vector<int> adj[200005], U, V, A, B;
map<pair<int, int>, bool> mp;
bool visited[200005];
queue<int> q;
int construct_roads(vector<int> X, vector<int> Y)
{
    int N=X.size();
    for (int i=0; i<N; i++)
        vec[Y[i]].push_back({X[i], i});
    for (int i=2; i<=2e5; i+=2)
    {
        if (vec[i].empty())
            continue;
        sort(vec[i].begin(), vec[i].end());
        if (vec[i].size()==1)
        {
            int ind=-1;
            for (int j=0; j<vec[i-2].size(); j++)
            {
                if (vec[i-2][j].first==vec[i][0].first)
                {
                    ind=j;
                    break;
                }
            }
            if (ind>=0)
                edge.push_back({vec[i-2][ind].second, vec[i][0].second});
        }
        else if (vec[i].size()==2)
        {
            if (vec[i][0].first==2 && vec[i][1].first==4)
            {
                int ind=-1;
                for (int j=0; j<vec[i-2].size(); j++)
                {
                    if (vec[i-2][j].first<=4)
                    {
                        ind=j;
                        break;
                    }
                }
                if (ind>=0)
                {
                    if (vec[i-2][ind].first==2)
                        edge.push_back({vec[i-2][ind].second, vec[i][0].second});
                    else
                        edge.push_back({vec[i-2][ind].second, vec[i][1].second});
                }
            }
            else if (vec[i][0].first==4 && vec[i][1].first==6)
            {
                int ind=-1;
                for (int j=0; j<vec[i-2].size(); j++)
                    if (vec[i-2][j].first>=4)
                        ind=j;
                if (ind>=0)
                {
                    if (vec[i-2][ind].first==4)
                        edge.push_back({vec[i-2][ind].second, vec[i][0].second});
                    else
                        edge.push_back({vec[i-2][ind].second, vec[i][1].second});
                }
            }
            else
            {
                for (int k=0; k<2; k++)
                {
                    int ind=-1;
                    for (int j=0; j<vec[i-2].size(); j++)
                    {
                        if (vec[i-2][j].first==vec[i][k].first)
                        {
                            ind=j;
                            break;
                        }
                    }
                    if (ind>=0)
                        edge.push_back({vec[i-2][ind].second, vec[i][k].second});
                }
            }
        }
        else
        {
            if (vec[i-2].size())
            {
                if (vec[i-2][0].first==2)
                    edge.push_back({vec[i-2][0].second, vec[i][0].second});
                if (vec[i-2][vec[i-2].size()-1].first==6)
                    edge.push_back({vec[i-2][vec[i-2].size()-1].second, vec[i][2].second});
                if (vec[i-2].size()==1 && vec[i-2][0].first==4)
                    edge.push_back({vec[i-2][0].second, vec[i][1].second});
            }
        }
        if (vec[i].size()==2)
        {
            if (vec[i][0].first+2==vec[i][1].first)
                edge.push_back({vec[i][0].second, vec[i][1].second});
        }
        else if (vec[i].size()==3)
        {
            edge.push_back({vec[i][0].second, vec[i][1].second});
            edge.push_back({vec[i][1].second, vec[i][2].second});
        }
    }
    for (int i=0; i<edge.size(); i++)
    {
        int u=edge[i].first, v=edge[i].second;
        adj[u].push_back(v);
        adj[v].push_back(u);
        U.push_back(u);
        V.push_back(v);
        if (X[u]==X[v])
        {
            if (mp[{X[u]-1, Y[u]+1}])
            {
                A.push_back(X[u]+1);
                B.push_back(Y[u]+1);
                mp[{X[u]+1, Y[u]+1}]=1;
            }
            else
            {
                A.push_back(X[u]-1);
                B.push_back(Y[u]+1);
                mp[{X[u]-1, Y[u]+1}]=1;
            }
        }
        else
        {
            if (mp[{X[u]+1, Y[u]-1}])
            {
                A.push_back(X[u]+1);
                B.push_back(Y[u]+1);
                mp[{X[u]+1, Y[u]+1}]=1;
            }
            else
            {
                A.push_back(X[u]+1);
                B.push_back(Y[u]-1);
                mp[{X[u]+1, Y[u]-1}]=1;
            }
        }
    }
    q.push(0);
    visited[0]=1;
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int v:adj[u])
        {
            if (!visited[v])
            {
                q.push(v);
                visited[v]=1;
            }
        }
    }
    for (int i=0; i<N; i++)
        if (!visited[i])
            return 0;
    build(U, V, A, B);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:22:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |             for (int j=0; j<vec[i-2].size(); j++)
      |                           ~^~~~~~~~~~~~~~~~
parks.cpp:38:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |                 for (int j=0; j<vec[i-2].size(); j++)
      |                               ~^~~~~~~~~~~~~~~~
parks.cpp:57:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 for (int j=0; j<vec[i-2].size(); j++)
      |                               ~^~~~~~~~~~~~~~~~
parks.cpp:73:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |                     for (int j=0; j<vec[i-2].size(); j++)
      |                                   ~^~~~~~~~~~~~~~~~
parks.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (int i=0; i<edge.size(); i++)
      |                   ~^~~~~~~~~~~~

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