Submission #712502

#	Time	Username	Problem	Language	Result	Execution time	Memory
712502		danikoynov	Fountain Parks (IOI21_parks)	C++17	55 / 100	1824 ms	164288 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;
int N, par[maxn];
int find_leader(int v)
{
    return (v == par[v]) ? v : (par[v] = find_leader(par[v]));
}

bool unite(int v, int u)
{
    v = find_leader(v);
    u = find_leader(u);
    if (v == u)
        return false;
    par[u] = v;
    return true;
}

struct edge
{
    int v, u, a, b;
    pair < pair < int, int >, pair < int, int > > db;
};

vector < edge > edges;
map < pair < int, int >, int > mp;
map < pair < int, int >, set < int > > pos;
void add_edge(pair < int, int > p, pair < int, int > q, int i, int j)
{
    edge cur;
    cur.v = i;
    cur.u = j;
    edges.push_back(cur);
    if (p.first > q.first)
        swap(p, q);
    if (p.second > q.second)
        swap(p, q);
    pair < int, int > curd;
    if (p.first == q.first)
    {
        pos[make_pair(p.first - 1, p.second + 1)].insert((int)edges.size() - 1);
        pos[ {p.first + 1,p.second + 1}].insert((int)edges.size() - 1);

        edges.back().db = {{p.first - 1, p.second + 1}, {p.first + 1, p.second + 1}};
    }
    else
    {
        pos[ {p.first + 1,p.second - 1}].insert((int)edges.size() - 1);
        pos[ {p.first + 1, p.second + 1}].insert((int)edges.size() - 1);
        edges.back().db = {{p.first + 1, p.second + 1}, {p.first + 1, p.second - 1}};
    }

}

vector < int > from, to, cx, cy;

int construct_roads(std::vector<int> x, std::vector<int> y)
{
    N = x.size();

    for (int i = 0; i < N; i ++)
    {
        par[i] = i;
        mp[ {x[i], y[i]}] = i + 1;
    }

    for (int i = 0; i < N; i ++)
    {
        for (int dx = -2; dx <= 2; dx ++)
        {
            if (abs(dx) < 2)
                continue;
            pair < int, int > nb = {x[i], y[i]};
            nb.first += dx;
            if (mp[nb] != 0)
            {
                if (unite(mp[nb] - 1, i))
                {
                    add_edge({x[i], y[i]}, nb, i, mp[nb] - 1);
                }
            }

            nb.first -= dx;
            nb.second += dx;
            if (mp[nb] != 0)
            {
                if (unite(mp[nb] - 1, i))
                {
                    add_edge({x[i], y[i]}, nb, i, mp[nb] - 1);
                }
            }
        }
    }
    int val = find_leader(0);
    for (int i = 1; i < N; i ++)
        if (find_leader(i) != val)
        return 0;
    /**for (int i = 0; i < edges.size(); i ++)
    {
        cout << edges[i].v << " " << edges[i].u << " " << edges[i].db.first.first << " " << edges[i].db.first.second << " " << edges[i].db.second.first << " " << edges[i].db.second.second << endl;
        //if (pos[edges[i].db])
    }*/
    set < pair < int, int > > q[5];
    for (pair < pair < int, int >, set < int > > cur : pos)
    {
        q[cur.second.size()].insert(cur.first);
    }

    for (int step = 0; step < edges.size(); step ++)
    {
        int pt = 1;
        while(q[pt].empty())
        {
           /// cout << "pt " << pt << endl;
            pt ++;
        }

        pair < int, int > cur = *q[pt].begin();
        int index = *pos[cur].begin();


        edges[index].a = cur.first;
        edges[index].b = cur.second;
        pair < int, int > d1 = edges[index].db.first;
        pair < int, int > d2 = edges[index].db.second;

        if (pos[d1].find(index) != pos[d1].end())
        {
            q[pos[d1].size()].erase(d1);
            pos[d1].erase(index);
            if (d1 != cur)
            q[pos[d1].size()].insert(d1);
        }
        if (pos[d2].find(index) != pos[d2].end())
        {
            q[pos[d2].size()].erase(d2);
            pos[d2].erase(index);
            if (d2 != cur)
            q[pos[d2].size()].insert(d2);
        }




    }

    from.resize(edges.size());
    to.resize(edges.size());
    cx.resize(edges.size());
    cy.resize(edges.size());

    for (int i = 0; i < edges.size(); i ++)
    {
        from[i] = edges[i].v;
        to[i] = edges[i].u;
        cx[i] = edges[i].a;
        cy[i] = edges[i].b;
    }

    build(from, to, cx, cy);
    /**for (int i = 0; i < edges.size(); i ++)
    {
        cout << edges[i].v << " " << edges[i].u << endl;
    }*/
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:113:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for (int step = 0; step < edges.size(); step ++)
      |                        ~~~~~^~~~~~~~~~~~~~
parks.cpp:156:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     for (int i = 0; i < edges.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~

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