Submission #492425

#	Time	Username	Problem	Language	Result	Execution time	Memory
492425		dxz05	Fountain Parks (IOI21_parks)	C++17	15 / 100	425 ms	36924 KiB

parks

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

using namespace std;

const int N = 2e5 + 3e2;

#define all(x) (x).begin(), (x).end()

int p[N];

int find(int x){
    return (x == p[x] ? x : p[x] = find(p[x]));
}

bool unite(int x, int y){
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (rand() & 1) swap(x, y);
    p[x] = y;
    return true;
}

int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    if (n == 1) {
        build({}, {}, {}, {});
        return 1;
    }

    vector<int> perm(n);
    iota(all(perm), 0);
    sort(all(perm), [&](int i, int j){
        return x[i] < x[j] || x[i] == x[j] && y[i] < y[j];
    });

    iota(p, p + n, 0);

    map<pair<int, int>, int> id;
    for (int i = 0; i < n; i++){
        id[{x[i], y[i]}] = i;
    }

    vector<int> U, V, A(n - 1), B(n - 1);

    vector<int> dx = {2, 0};
    vector<int> dy = {0, 2};

    for (int it = 0; it < dx.size(); it++){
        for (int i : perm){
            int X = x[i] + dx[it], Y = y[i] + dy[it];
            if (id.find({X, Y}) != id.end()){
                int j = id[{X, Y}];
                if (!unite(i, j)) continue;
                U.push_back(i);
                V.push_back(j);
            }
        }
    }

    if (U.size() != n - 1) return 0;

    for (int it = 0; it < n - 1; it++){
        int i = U[it], j = V[it];
        if (x[i] == x[j]){
            B[it] = (y[i] + y[j]) / 2;
            if (x[i] == 2) A[it] = 1;
            if (x[i] == 6) A[it] = 7;
            if (x[i] == 4) B[it] = -1;
        } else {
            A[it] = (x[i] + x[j]) / 2;
            B[it] = y[i] + (A[it] == 3 ? -1 : 1);
        }
    }

    set<pair<int, int>> points;
    for (int it = 0; it < n - 1; it++){
        if (B[it] != -1) points.insert(make_pair(A[it], B[it]));
    }

    for (int it = 0; it < n - 1; it++){
        int i = U[it], j = V[it];
        if (x[i] == x[j] && x[i] == 4){
            int Y = (y[i] + y[j]) / 2;

            if (points.find({3, Y}) == points.end()) A[it] = 3;
            else A[it] = 5;

            B[it] = Y;
        }
    }

    build(U, V, A, B);

    return 1;
}

Compilation message (stderr)

parks.cpp: In lambda function:
parks.cpp:35:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |         return x[i] < x[j] || x[i] == x[j] && y[i] < y[j];
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:50:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int it = 0; it < dx.size(); it++){
      |                      ~~~^~~~~~~~~~~
parks.cpp:62:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |     if (U.size() != n - 1) return 0;
      |         ~~~~~~~~~^~~~~~~~

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