Submission #591911

#	Time	Username	Problem	Language	Result	Execution time	Memory
591911		Lucpp	Fountain Parks (IOI21_parks)	C++17	100 / 100	434 ms	42076 KiB

parks

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

vector<int> par;
int find(int i){
    if(i == par[i]) return i;
    else return par[i] = find(par[i]);
}
bool merge(int a, int b){
    a = find(a), b = find(b);
    if(a == b) return false; 
    par[a] = b;
    return true;
}

pair<int, int> getBench(int x1, int y1, int x2, int y2){
    if(x1 == x2){
        pair<int, int> a = {x1+1, (y1+y2)/2}, b = {x1-1, (y1+y2)/2};
        if((a.first + a.second) % 4 == 0) return a;
        else return b;
    }
    else{
        pair<int, int> a = {(x1+x2)/2, y1+1}, b = {(x1+x2)/2, y1-1};
        if((a.first + a.second) % 4 == 2) return a;
        else return b;
    }
}

int construct_roads(vector<int> vx, vector<int> vy) {
    if (vx.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    int n = (int)vx.size();
    par.resize(n);
    for(int i = 0; i < n; i++) par[i] = i;
    vector<tuple<int, int, int>> p;
    map<pair<int, int>, int> mp;
    for(int i = 0; i < n; i++){
        p.emplace_back(vx[i], vy[i], i);
        mp[make_pair(vx[i], vy[i])] = i;
    }
    int sz = 0;
    set<pair<int, int>> benches;
    sort(p.begin(), p.end());
    vector<int> dx = {-2, 0}, dy = {0, -2};
    vector<int> u, v, a, b;
    for(auto [x, y, i] : p){
        for(int j = 0; j < 2; j++){
            int x2 = x+dx[j], y2 = y+dy[j];
            if(!mp.count(make_pair(x2, y2))) continue;
            int k = mp[make_pair(x2, y2)];
            auto bench = getBench(x, y, x2, y2);
            if(benches.count(bench)) continue;
            if(merge(i, k)){
                sz++;
                u.push_back(i);
                v.push_back(k);
                a.push_back(bench.first);
                b.push_back(bench.second);
                benches.insert(bench);
            }
        }
    }
    if(sz != n-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