Submission #814388

#	Time	Username	Problem	Language	Result	Execution time	Memory
814388		LittleCube	Fountain Parks (IOI21_parks)	C++17	70 / 100	886 ms	72184 KiB

parks

#pragma GCC optimize("Ofast,unroll-loops")
#include "parks.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

map<pii, int> id;
int n, m, deg[200000], dsu[200000], vis[400001], use[400001], hmm;
pii pos[400001];
vector<pair<pii, pii>> edge;
vector<pii> E[400001];
vector<int> ru, rv, bx, by;

int find(int k)
{
    return dsu[k] == k ? k : dsu[k] = find(dsu[k]);
}

void merge(int x, int y)
{
    x = find(x), y = find(y);
    dsu[x] = y;
}

int node(int x, int y)
{
    if (!id[pii(x, y)])
    {
        id[pii(x, y)] = ++m;
        pos[m] = pii(x, y);
    }
    return id[pii(x, y)];
}

void dfs(int u, int p)
{
    vis[u] = 1;
    int flag = 1;
    for (auto [v, i] : E[u])
        if (!vis[v])
            dfs(v, u);
    hmm += E[u].size();
    hmm -= 2;
    for (auto [v, i] : E[u])
        if (v != p && !use[i] && flag)
        {
            flag--;
            use[i] = 1;
            tie(bx[i], by[i]) = pos[u];
        }
    for (auto [v, i] : E[u])
        if (!use[i] && flag)
        {
            flag--;
            use[i] = 1;
            tie(bx[i], by[i]) = pos[u];
        }
}

int construct_roads(vector<int> x, vector<int> y)
{
    n = x.size();
    for (int i = 0; i < n; i++)
        dsu[i] = i;
    for (int i = 0; i < n; i++)
        id[pii(x[i], y[i])] = i + 1;

    bx.resize(n - 1), by.resize(n - 1);
    for (int i = 0; i < n; i++)
    {
        if (id.find(pii(x[i], y[i] - 2)) != id.end())
        {
            int j = id[pii(x[i], y[i] - 2)] - 1;
            merge(i, j);
            ru.emplace_back(i);
            rv.emplace_back(j);
        }
        if (id.find(pii(x[i] - 2, y[i])) != id.end())
        {
            int j = id[pii(x[i] - 2, y[i])] - 1;
            edge.emplace_back(make_pair(pii(x[i] - 1, y[i]), pii(i, j)));
        }
    }
    sort(edge.begin(), edge.end(), [&](pair<pii, pii> f, pair<pii, pii> s)
         {
        pii p = f.F, q = s.F;
        if(p.F != q.F)
            return p.F < q.F;
        if(p.F % 4 == 1)
            return p.S < q.S;
        return p.S > q.S; });
    mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
    shuffle(edge.begin(), edge.end(), rd);
    for (auto [_, p] : edge)
    {
        auto [u, v] = p;
        if (find(u) != find(v))
        {
            ru.emplace_back(u);
            rv.emplace_back(v);
            merge(u, v);
        }
    }
    if (ru.size() < n - 1)
        return 0;
    id.clear();
    for (int i = 0; i < n - 1; i++)
    {
        int u = ru[i], v = rv[i];
        if (x[u] == x[v])
        {
            int a = node(x[u] - 1, (y[u] + y[v]) / 2),
                b = node(x[u] + 1, (y[u] + y[v]) / 2);
            E[a].emplace_back(pii(b, i));
            E[b].emplace_back(pii(a, i));
        }
        else
        {
            int a = node((x[u] + x[v]) / 2, y[u] + 1),
                b = node((x[u] + x[v]) / 2, y[u] - 1);
            E[a].emplace_back(pii(b, i));
            E[b].emplace_back(pii(a, i));
        }
    }
    for (int i = 1; i <= m; i++)
        if (!vis[i])
        {
            hmm = 0;
            dfs(i, i);
        }
    for (int i = 0; i < n - 1; i++)
        if(!use[i])
            return 0;
    build(ru, rv, bx, by);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:108:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  108 |     if (ru.size() < n - 1)
      |         ~~~~~~~~~~^~~~~~~

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