Submission #492420

#	Time	Username	Problem	Language	Result	Execution time	Memory
492420		dxz05	Fountain Parks (IOI21_parks)	C++17	15 / 100	611 ms	28276 KiB

parks

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

using namespace std;

const int N = 2e5 + 3e2;

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;
    }

    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, B;

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

    for (int i = 0; i < n; i++){
        for (int it = 0; it < 4; it++){
            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 (y[i] == y[j]){
            A.push_back((x[i] + x[j]) / 2);
            B.push_back(y[i] + 1);
        } else {
            A.push_back((x[i] == 2 ? 1 : 5));
            B.push_back((y[i] + y[j]) / 2);
        }
    }

    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:54:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |     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