Submission #1198511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198511		HappyCapybara	Fountain Parks (IOI21_parks)	C++17	45 / 100	548 ms	99752 KiB

parks

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

#define ll long long

ll h(ll x, ll y){
    return x*200001+y;
}

pair<int,int> rh(ll x){
    return {x/200001, x%200001};
}

vector<int> p;

int find(int a){
    if (a == p[a]) return p[a];
    return p[a] = find(p[a]);
}

void merge(int a, int b){
    a = find(a);
    b = find(b);
    p[b] = a;
}

int construct_roads(vector<int> x, vector<int> y){
    int n = x.size();
    map<int,vector<pair<int,int>>> rows, cols;
    for (int i=0; i<n; i++){
        rows[x[i]].push_back({y[i], i});
        cols[y[i]].push_back({x[i], i});
    }
    vector<pair<ll,ll>> btt;
    map<ll,set<int>> ttb;
    vector<pair<int,int>> e;
    for (auto [i, v] : rows){
        sort(v.begin(), v.end());
        for (int j=0; j+1<v.size(); j++){
            if (v[j].first+2 == v[j+1].first){
                e.push_back({v[j].second, v[j+1].second});
                btt.push_back({h(i-1, v[j].first+1), h(i+1, v[j].first+1)});
                ttb[h(i-1, v[j].first+1)].insert((int)e.size()-1);
                ttb[h(i+1, v[j].first+1)].insert((int)e.size()-1);
            }
        }
    }
    for (auto [i, v] : cols){
        sort(v.begin(), v.end());
        for (int j=0; j+1<v.size(); j++){
            if (v[j].first+2 == v[j+1].first){
                e.push_back({v[j].second, v[j+1].second});
                btt.push_back({h(v[j].first+1, i-1), h(v[j].first+1, i+1)});
                ttb[h(v[j].first+1, i-1)].insert((int)e.size()-1);
                ttb[h(v[j].first+1, i+1)].insert((int)e.size()-1);
            }
        }
    }
    p.resize(n);
    for (int i=0; i<n; i++) p[i] = i;
    set<int> todo;
    queue<int> ready;
    for (int i=0; i<e.size(); i++){
        todo.insert(i);
        if (ttb[btt[i].first].size() == 1 || ttb[btt[i].second].size() == 1) ready.push(i);
    }
    vector<int> u, v, a, b;
    while (!todo.empty()){
        if (0){
            int cur = ready.front();
            ready.pop();
            if (todo.find(cur) == todo.end()) continue;
            todo.erase(cur);
            int i = e[cur].first, j = e[cur].second;
            if (find(i) != find(j)){
                u.push_back(i);
                v.push_back(j);
                pair<int,int> tree;
                if (ttb[btt[cur].first].size() == 1){
                    tree = rh(btt[cur].first);
                    ttb[btt[cur].second].erase(cur);
                    if (ttb[btt[cur].second].size() == 1) ready.push(*ttb[btt[cur].second].begin());
                }
                else {
                    tree = rh(btt[cur].second);
                    ttb[btt[cur].first].erase(cur);
                    if (ttb[btt[cur].first].size() == 1) ready.push(*ttb[btt[cur].first].begin());
                }
                a.push_back(tree.first);
                b.push_back(tree.second);
                merge(i, j);
            }
            else {
                ttb[btt[cur].first].erase(cur);
                if (ttb[btt[cur].first].size() == 1) ready.push(*ttb[btt[cur].first].begin());
                ttb[btt[cur].second].erase(cur);
                if (ttb[btt[cur].second].size() == 1) ready.push(*ttb[btt[cur].second].begin());
            }
            continue;
        }
        int cur = *todo.begin();
        todo.erase(cur);
        int i = e[cur].first, j = e[cur].second;
        if (find(i) != find(j)){
            u.push_back(i);
            v.push_back(j);
            if (x[i] == x[j]){
                b.push_back((y[i]+y[j])/2);
                int rp = ((x[i]+1)/2+b.back()/2) % 2;
                if (rp){
                    a.push_back(x[i]+1);
                    ttb[btt[cur].first].erase(cur);
                    if (ttb[btt[cur].first].size() == 1) ready.push(*ttb[btt[cur].first].begin());
                }
                else {
                    a.push_back(x[i]-1);
                    ttb[btt[cur].second].erase(cur);
                    if (ttb[btt[cur].second].size() == 1) ready.push(*ttb[btt[cur].second].begin());
                }
            }
            else {
                a.push_back((x[i]+x[j])/2);
                int up = ((y[i]+1)/2+a.back()/2) % 2;
                if (up){
                    b.push_back(y[i]-1);
                    ttb[btt[cur].second].erase(cur);
                    if (ttb[btt[cur].second].size() == 1) ready.push(*ttb[btt[cur].second].begin());
                }
                else {
                    b.push_back(y[i]+1);
                    ttb[btt[cur].first].erase(cur);
                    if (ttb[btt[cur].first].size() == 1) ready.push(*ttb[btt[cur].first].begin());
                }
            }
            merge(i, j);
        }
        else {
            ttb[btt[cur].first].erase(cur);
            if (ttb[btt[cur].first].size() == 1) ready.push(*ttb[btt[cur].first].begin());
            ttb[btt[cur].second].erase(cur);
            if (ttb[btt[cur].second].size() == 1) ready.push(*ttb[btt[cur].second].begin());
        }
    }
    for (int i=0; i<n; i++){
        if (find(i) != find(0)) return 0;
    }
    build(u, v, a, b);
    return 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