Submission #1021027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021027		Blistering_Barnacles	Fountain Parks (IOI21_parks)	C++17	15 / 100	478 ms	45152 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;
    };
    auto cmp = [&](pair<int, int> a, pair<int, int> b){
        auto [i1, j1] = a;
        auto [i2, j2] = b;
        if(x[i1] == x[j1]){
            if(x[i2] == x[j2]){
                return x[i1] < x[i2];
            }
            else{
                return x[i1] < max(x[i2], x[j2]);
            }
        }
        else{
            if(x[i2] == x[j2]){
                return min(x[i1], x[j1]) < x[i2];
            }
            else{
                return min(x[i1], x[j1]) < min(x[i2], x[j2]);
            }
        }
    };
    sort(e.begin(), e.end(), cmp);
    map<pair<int, int>, bool> vis;
    for(auto [i, j]: e){
        if(mrg(i, j)){
            u.push_back(i), v.push_back(j);
            if(x[i] == x[j]){
                if(!vis.count({x[i] - 1, max(y[i], y[j]) - 1})){
                    vis[{x[i] - 1, max(y[i], y[j]) - 1}] = 1;
                    a.push_back(x[i] - 1);
                    b.push_back(max(y[i], y[j]) - 1);
                }
                else{
                    vis[{x[i] + 1, max(y[i], y[j]) - 1}] = 1;
                    a.push_back(x[i] + 1);
                    b.push_back(max(y[i], y[j]) - 1);
                }
            }
            else{
                if(!vis.count({max(x[i], x[j]) - 1, y[i] - 1})){
                    vis[{max(x[i], x[j]) - 1, y[i] - 1}] = 1;
                    a.push_back(max(x[i], x[j]) - 1);
                    b.push_back(y[i] - 1);
                }
                else{
                    vis[{max(x[i], x[j]) - 1, y[i] + 1}] = 1;
                    a.push_back(max(x[i], x[j]) - 1);
                    b.push_back(y[i] + 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