Submission #446394

#	Time	Username	Problem	Language	Result	Execution time	Memory
446394		luciocf	Fountain Parks (IOI21_parks)	C++17	15 / 100	201 ms	22552 KiB

parks

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

using namespace std;

const int maxn = 2e5+10;

struct Pt
{
    int x, y, ind;
} a[maxn];

struct Road
{
    int u, v, x, y;
} road[maxn];

struct DSU
{
    int pai[maxn], peso[maxn];

    void init(int n)
    {
        for (int i = 1; i <= n; i++)
            pai[i] = i;
    }

    int Find(int x)
    {
        if (pai[x] == x) return x;
        return pai[x] = Find(pai[x]);
    }

    void Join(int x, int y)
    {
        if (x == y) return;

        if (peso[x] < peso[y]) swap(x, y);

        pai[y] = x, peso[x] += peso[y]; 
    }
} dsu;

bool comp(Pt a, Pt b)
{
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

bool comp2(Pt a, Pt b)
{
    if (a.y == b.y) return a.x < b.x;
    return a.y < b.y;
}

int construct_roads(vector<int> X, vector<int> Y)
{
    int n = X.size();
    bool sub = 1;

    int mx = 0;

    for (int i = 1; i <= n; i++)
    {
        a[i] = {X[i-1], Y[i-1], i};

        mx = max(mx, a[i].x);
    }

    if (mx > 6) sub = 0;

    dsu.init(n);

    if (sub)
    {
        sort(a+1, a+n+1, comp);

        int ind = 0, cc = n;

        for (int i = 1; i < n; i++)
        {
            if (a[i].x == a[i+1].x && a[i].y+2 == a[i+1].y)
            {
                dsu.Join(a[i].ind, a[i+1].ind), cc--;

                road[++ind] = {a[i].ind, a[i+1].ind, a[i].x-1, a[i].y+1};

                if (a[i].x == mx) road[ind].x = a[i].x+1, a[i].y+1;
            }
        }

        sort(a+1, a+n+1, comp2);

        for (int i = 1; i < n; i++)
        {
            if (dsu.Find(a[i].ind) != dsu.Find(a[i+1].ind) && a[i].y == a[i+1].y && a[i].x+2 == a[i+1].x)
            {
                dsu.Join(a[i].ind, a[i+1].ind), cc--;
                road[++ind] = {a[i].ind, a[i+1].ind, a[i].x+1, a[i].y+1};
            }
        }

        if (cc != 1) return 0;

        vector<int> U, V, A, B;

        for (int i = 1; i < n; i++)
        {
            U.push_back(road[i].u-1), V.push_back(road[i].v-1);
            A.push_back(road[i].x), B.push_back(road[i].y);
        }

        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:88:65: warning: right operand of comma operator has no effect [-Wunused-value]
   88 |                 if (a[i].x == mx) road[ind].x = a[i].x+1, a[i].y+1;
      |                                                           ~~~~~~^~
parks.cpp:116:1: warning: control reaches end of non-void function [-Wreturn-type]
  116 | }
      | ^

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