Submission #623193

#	Time	Username	Problem	Language	Result	Execution time	Memory
623193		Hanksburger	Fountain Parks (IOI21_parks)	C++17	15 / 100	588 ms	76012 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[200005], X, Y, U, V, A, B;
vector<pair<int, int> > edge;
map<pair<int, int>, bool> mp;
map<pair<int, int>, int> p;
bool visited[200005];
queue<int> q;
bool cmp(pair<int, int> u, pair<int, int> v)
{
    if (X[u.first]!=X[v.first] || X[u.second]!=X[v.second])
        return (X[u.first]<X[v.first] || X[u.second]<X[v.second]);
    return Y[u.first]<Y[v.first];
}
int construct_roads(vector<int> x, vector<int> y)
{
    int N=x.size();
    for (int i=0; i<N; i++)
    {
        X.push_back(x[i]);
        Y.push_back(y[i]);
        p[{X[i], Y[i]}]=i+1;
    }
    for (auto itr=p.begin(); itr!=p.end(); itr++)
    {
        int ind=itr->second-1;
        if (p[{X[ind]-2, Y[ind]}])
            edge.push_back({p[{X[ind]-2, Y[ind]}]-1, ind});
        if (p[{X[ind], Y[ind]-2}])
            edge.push_back({p[{X[ind], Y[ind]-2}]-1, ind});
    }
    sort(edge.begin(), edge.end(), cmp);
    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:34: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]
   34 |     for (int i=0; i<edge.size(); i++)
      |                   ~^~~~~~~~~~~~

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