Submission #800350

#	Time	Username	Problem	Language	Result	Execution time	Memory
800350		TheSahib	Fountain Parks (IOI21_parks)	C++17	0 / 100	1 ms	1460 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;
    }
    set<pii> 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.insert({x[i] + d.first, y[i] + d.second});
                }
            }
        }
    }
    if(comp != 1){
        return 0;
    }
    map<pii, int> mp;
    vector<pii> abc;
    for(auto& p:roads){
        for(pii d:dir){
            pii b = {p.first + d.first, p.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, b;
    while(abc.size() && a.size() < v.size()){
        pii p = abc.back();
        mp[p]--;
        abc.pop_back();
        
        a.push_back(p.first);
        b.push_back(p.second);
        
        for(pii d:dir){
            pii b = {p.first + d.first, p.second + d.second};
            if(roads.count(b)){
                b.first += d.first;
                b.second += d.second;
                mp[b] -= 1;
                if(mp[b] == 1){
                    abc.push_back(b);
                }
                roads.erase(b);
                break;
            }
        }
    }
    if(abc.empty() && a.size() < v.size()){
        for(auto& p:mp){
            if(p.second == 0) continue;
            a.push_back(p.first.first);
            b.push_back(p.first.second);
        }
    }
    
    build(u, v, a, b);
    return 1;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30