제출 #1198556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198556		HappyCapybara	Fountain Parks (IOI21_parks)	C++17	100 / 100	1364 ms	124188 KiB

parks

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

#define ll long long

ll k = 1ll<<20;

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

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

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, mv;
    queue<int> ready;
    for (int i=0; i<e.size(); i++){
        todo.insert(i);
        mv.insert(i);
        if (ttb[btt[i].first].size() == 1 || ttb[btt[i].second].size() == 1) ready.push(i);
    }
    vector<int> u, v, a, b;
    set<ll> done;
    while (!todo.empty()){
        if (!ready.empty()){
            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);
                done.insert(h(a.back(), b.back()));
                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;
        }
        else {
            bool fts = false;
            int cur = *todo.begin();
            if (!mv.empty()){
                cur = *mv.begin();
                mv.erase(cur);
                fts = true;
            }
            if (todo.find(cur) == todo.end()) continue;
            int i = e[cur].first, j = e[cur].second;
            if (find(i) != find(j)){
                pair<int,int> des;
                if (x[i] == x[j]){
                    des.second = (y[i]+y[j])/2;
                    int rp = ((x[i]+1)/2+des.second/2) % 2;
                    if (rp) des.first = x[i]+1;
                    else des.first = x[i]-1;
                }
                else {
                    des.first = (x[i]+x[j])/2;
                    int up = ((y[i]+1)/2+des.first/2) % 2;
                    if (up) des.second = y[i]-1;
                    else des.second = y[i]+1;
                }
                if (done.find(h(des.first, des.second)) != done.end()){
                    if (fts) continue;
                    ll cringe = btt[cur].first;
                    if (cringe == h(des.first, des.second)) cringe = btt[cur].second;
                    des = rh(cringe);
                }
                if (done.find(h(des.first, des.second)) == done.end()){
                    u.push_back(i);
                    v.push_back(j);
                    a.push_back(des.first);
                    b.push_back(des.second);
                    done.insert(h(a.back(), b.back()));
                    merge(i, j);
                    todo.erase(cur);
                    ll tbd = btt[cur].first;
                    if (tbd == h(des.first, des.second)) tbd = btt[cur].second;
                    ttb[tbd].erase(cur);
                    if (ttb[tbd].size() == 1) ready.push(*ttb[tbd].begin());
                }
            }
            else {
                todo.erase(cur);
                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: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30