Submission #1256049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256049		altern23	Fountain Parks (IOI21_parks)	C++20	100 / 100	357 ms	44400 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5;
int par[MAXN + 5];

vector<int> u, v, a, b;

map<pair<int, int>, int> mp;
map<pair<int, int>, bool> used;

int find(int idx){
    return (par[idx] == idx ? idx : par[idx] = find(par[idx]));
}

void join(int A, int B, int X, int Y){
    int lstA = A, lstB = B;
    A = find(A), B = find(B);
    if(A == B || used.count({X, Y})) return;
    a.push_back(X), b.push_back(Y);
    u.push_back(lstA), v.push_back(lstB);
    par[B] = A;
    used[{X, Y}] = 1;
}

int construct_roads(vector<int> x, vector<int> y) {
    int N = x.size();
    vector<pair<pair<int, int>, int>> coords;
    for(int i = 0; i < N; i++){
        coords.push_back({{x[i], y[i]}, i});
        mp[{x[i], y[i]}] = i;
        par[i] = i;
    }
    sort(coords.begin(), coords.end());
    for(auto [i, j] : coords){
        int parity = (i.first + i.second) % 4;
        // kiri
        if(mp.count({i.first, i.second - 2})){
            join(j, mp[{i.first, i.second - 2}], i.first + (parity ? 1 : -1), i.second - 1);
        }
        // bawah
        if(mp.count({i.first - 2, i.second})){
            join(j, mp[{i.first - 2, i.second}], i.first - 1, i.second + (parity ? -1 : 1));
        }
    }

    int cc = 0;
    for(int i = 0; i < N; i++){
        cc += (i == find(i));
    }
    
    if(cc > 1) return 0;
    build(u, v, a, b);
    return 1;
}

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