Submission #441433

#	Time	Username	Problem	Language	Result	Execution time	Memory
441433		SorahISA	Fountain Parks (IOI21_parks)	C++17	45 / 100	983 ms	68408 KiB

parks

#include "parks.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

// #define int long long
// #define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

// #define X first
// #define Y second
#define eb emplace_back
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

namespace {

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2E5 + 5;
const int dx[] = {2, 0, -2,  0};
const int dy[] = {0, 2,  0, -2};

map<pii, int> fountain, bench;
// map<pii, vector<int>> candidate;
vector<int> p(maxn);

vector<int> adj[maxn];

int R(int x) {return x ^ p[x] ? p[x] = R(p[x]) : x;}
int U(int x, int y) {x = R(x), y = R(y); return x ^ y ? p[x] = y, 1 : 0;}

} /// end of namespace

int construct_roads(vector<int> X, vector<int> Y) {
    int N = X.size();
    vector<int> u, v, a, b;
    
    if (N == 1) return build({}, {}, {}, {}), 1;
    
    iota(ALL(p), 0);
    for (int i = 0; i < N; ++i) fountain[{X[i], Y[i]}] = i+1;
    for (int i = 0; i < N; ++i) {
        for (int d = 0; d < 4; ++d) {
            int nei = fountain[{X[i] + dx[d], Y[i] + dy[d]}];
            if (nei-1 > i and U(i, nei-1)) u.eb(i), v.eb(nei-1);
        }
    }
    for (int i = 0; i < N; ++i) if (R(i) != R(0)) return 0;
    
    int M = u.size(); a.assign(M, -1), b.assign(M, -1);
    assert(M == N-1);
    
    // for (int i = 0; i < M; ++i) {
        // if (X[u[i]] == X[v[i]]) {
            // int midY = Y[u[i]] + Y[v[i]] >> 1;
            // candidate[{X[u[i]] + 1, midY}].eb(i);
            // candidate[{X[u[i]] - 1, midY}].eb(i);
        // }
        // else if (Y[u[i]] == Y[v[i]]) {
            // int midX = X[u[i]] + X[v[i]] >> 1;
            // candidate[{midX, Y[u[i]] + 1}].eb(i);
            // candidate[{midX, Y[u[i]] - 1}].eb(i);
        // }
    // }
    
    // for (auto [coord, vec] : candidate) {
        // if (vec.size() >= 2) {
            // for (auto x : vec) for (auto y : vec) {
                // if (x < y) adj[x].eb(y);
            // }
        // }
    // }
    
    for (int i = 0; i < M; ++i) {
        if (X[u[i]] == X[v[i]]) {
            int midY = Y[u[i]] + Y[v[i]] >> 1;
            if (min(Y[u[i]], Y[v[i]]) % 4 == X[u[i]] % 4) a[i] = X[u[i]] + 1;
            else a[i] = X[u[i]] - 1;
            b[i] = midY;
            bench[{a[i], b[i]}] = 1;
        }
    }
    
    for (int i = 0; i < M; ++i) {
        if (Y[u[i]] == Y[v[i]]) {
            int midX = X[u[i]] + X[v[i]] >> 1;
            a[i] = midX;
                 if (!bench[{midX, Y[u[i]] + 1}]) b[i] = Y[u[i]] + 1;
            else if (!bench[{midX, Y[v[i]] - 1}]) b[i] = Y[v[i]] - 1;
            bench[{a[i], b[i]}] = 1;
        }
    }
    
    return build(u, v, a, b), 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:83:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |             int midY = Y[u[i]] + Y[v[i]] >> 1;
parks.cpp:93:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |             int midX = X[u[i]] + X[v[i]] >> 1;

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