Submission #1021009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021009		Blistering_Barnacles	Fountain Parks (IOI21_parks)	C++17	15 / 100	330 ms	32308 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int construct_roads(vector<int> x, vector<int> y) {
    if (x.size() == 1) {
    build({}, {}, {}, {});
        return 1;
    }
    map<pair<int, int>, int> mp;
    vector<int> u, v, a, b;
    vector<pair<int, int>> e;
    int n = (int)x.size();
    for(int i = 0; i < n; i++){
        if(mp.count({x[i], y[i] - 2})){
            e.push_back({mp[{x[i], y[i] - 2}], i});
        }
        if(mp.count({x[i], y[i] + 2})){
            e.push_back({mp[{x[i], y[i] + 2}], i});
        }
        if(mp.count({x[i] - 2, y[i]})){
            e.push_back({mp[{x[i] - 2, y[i]}], i});
        }
        if(mp.count({x[i] + 2, y[i]})){
            e.push_back({mp[{x[i] + 2, y[i]}], i});
        }
        mp[{x[i], y[i]}] = i;
    }
    vector<int> par(n, -1);
    function<int(int)> getpar = [&](int x){
        return (par[x] < 0 ? x : par[x] = getpar(par[x]));
    };
    auto mrg = [&](int x, int y){
        x = getpar(x), y = getpar(y);
        if(x == y)return false;
        if(par[x] > par[y])swap(x, y);
        par[x] += par[y], par[y] = x;
        return true;
    };
    for(auto [i, j]: e){
        if(mrg(i, j)){
            u.push_back(i), v.push_back(j);
            a.push_back((x[i] != x[j] ? 3 : (x[i] == 2 ? 1 : 5)));
            b.push_back(max(y[i], y[j]) - 1);
        }
    }
    int cnt = 0;
    for(int i = 0; i < n; i++)cnt += par[i] < 0;
    if(cnt > 1)return 0;
    build(u, v, a, b);
    return 1;
}

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