Submission #483983

#	Time	Username	Problem	Language	Result	Execution time	Memory
483983		rumen_m	Fountain Parks (IOI21_parks)	C++17	100 / 100	487 ms	57692 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
struct fountains
{
    int x,y;
    int id;
};
vector <fountains> A;
vector <int> u,v,a,b;
const int maxn = 2e5+5;
bool cmp(fountains i, fountains j)
{
    if(i.y==j.y)return i.x<j.x;
    return i.y<j.y;
}
map <pair <int,int> , int> mp;
set <pair <int,int> > st;
vector <int> g[maxn];
bool vis[maxn];
void dfs(int v)
{
    vis[v] = 1;
    for(auto u: g[v])
    {
        if(!vis[u])dfs(u);
    }
}
int construct_roads(std::vector<int> x, std::vector<int> y) {

   A.resize(x.size());
   int i;
   for(i=0;i<x.size();i++)
   {
       A[i].x = x[i];
       A[i].y = y[i];
       A[i].id = i;
   }
   sort(A.begin(),A.end(),cmp);
   int n = A.size();
   for(i=0;i<n;i++)
   {
       mp[{A[i].x,A[i].y}] = i;
   }
   for(i=0;i<n;i++)
   {
       int x = A[i].x;
       int y = A[i].y;
       y-=2;
       if(mp.find({x,y})!=mp.end())
        {
            int k = mp[{x,y}];
            int px,py;

            py = y+1;
            if((y+1+x-1)%4==0)px = x-1;
            else
                px = x+1;
            if(st.find({px,py})==st.end())
                {
                    st.insert({px,py});
                    g[k].push_back(i);
            g[i].push_back(k);
            u.push_back(A[k].id);
            v.push_back(A[i].id);
            a.push_back(px);
            b.push_back(py);
                }

        }
        y+=2;
        x-=2;
         if(mp.find({x,y})!=mp.end())
        {
            int k = mp[{x,y}];
            int px,py;

            px = x+1;
            if((y-1+x+1)%4!=0)py= y-1;
            else
                py = y+1;
            if(st.find({px,py})==st.end())
                {
                    st.insert({px,py});
                    g[k].push_back(i);
            g[i].push_back(k);
             u.push_back(A[k].id);
            v.push_back(A[i].id);
            a.push_back(px);
            b.push_back(py);
                }

        }
   }
   dfs(0);
   for(i=1;i<n;i++)
   {
       if(!vis[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:33:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    for(i=0;i<x.size();i++)
      |            ~^~~~~~~~~

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