Submission #800383

#	Time	Username	Problem	Language	Result	Execution time	Memory
800383		TheSahib	Fountain Parks (IOI21_parks)	C++17	15 / 100	992 ms	63152 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>


using namespace std;


const int MAX = 3e5 + 5;
pii dir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int n = 0;
int comp = 0;
int par[MAX];

int get(int node){
    if(par[node] < 0) return node;
    return par[node] = get(par[node]);
}

bool unite(int v, int u){
    v = get(v);
    u = get(u);
    if(v == u) return false;
    if(-par[v] < -par[u]) swap(v, u);
    par[v] += par[u];
    par[u] = v;
    comp--;
    return true;
}

map<pii, int> f;

int construct_roads(vector<int> x, vector<int> y) {
    memset(par, -1, sizeof(par));
    n = x.size();
    comp = n;
    for (int i = 0; i < n; i++)
    {
        f[{x[i], y[i]}] = i;
    }
    map<pii, int> roads;
    vector<int> v, u;
    for (int i = 0; i < n && comp > 1; i++)
    {
        for(pii d:dir){
            pii p = {x[i] + d.first * 2, y[i] + d.second * 2};
            if(f.count(p)){
                int idx = f[p];
                if(unite(i, idx)){
                    v.push_back(i);
                    u.push_back(idx);
                    roads[{x[i] + d.first, y[i] + d.second}] = v.size() - 1;
                }
            }
        }
    }
    if(comp != 1){
        return 0;
    }
    map<pii, int> mp;
    vector<pii> abc;
    for(auto& p:roads){
        for(pii d:dir){
            pii b = {p.first.first + d.first, p.first.second + d.second};
            if(f.count(b)) continue;
            mp[b]++;
        }
    }
    for(auto& p:mp){
        if(p.second == 1) {
            abc.push_back(p.first);
            roads.erase(p.first);
        }
    }
    vector<int> a(n - 1), b(n - 1);
    while(abc.size()){
        pii p = abc.back();
        abc.pop_back();
        
        if(mp[p] == 0) continue;
        mp[p]--;
        
        for(pii d:dir){
            pii c = {p.first + d.first, p.second + d.second};
            if(roads.count(c)){
                int idx = roads[c];
                a[idx] = p.first;
                b[idx] = p.second;

                roads.erase(c);

                c.first += d.first;
                c.second += d.second;
                
                mp[c] -= 1;
                if(mp[c] == 1){
                    abc.push_back(c);
                }
                break;
            }
        }
    }
    for(auto& p:mp){
        if(p.second <= 0) continue;
        for(pii d:dir){
            pii c = {p.first.first + d.first, p.first.first + d.second};
            if(roads.count(c)){
                int idx = roads[c];
                a[idx] = p.first.first;
                b[idx] = p.first.second;

                roads.erase(c);
                break;
            }
        }
    }
    
    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