Submission #1051920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051920		amine_aroua	Fountain Parks (IOI21_parks)	C++17	15 / 100	327 ms	39048 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
struct DSU 
{
    vector<int> e;
    DSU(int n)
    {
        e.assign(n , -1);
    }
    int get(int u )
    {
        return (e[u] < 0 ? u : e[u] = get(e[u]));
    }
    bool same(int u , int v)
    {
        return get(u) == get(v);
    }
    bool unite(int u , int v)
    {
        u = get(u ) , v =get(v);
        if(u == v)
            return 0;
        if(e[u] > e[v])
            swap(u , v);
        e[u]+=e[v];
        e[v] = u;
        return 1;
    }
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int construct_roads(std::vector<int> x, std::vector<int> y) {
    int n= (int)x.size();
    vector<int> u , v , a , b;
    map<pair<int, int> , int> idx;
    set<pair<int ,int>> taken;
    for(int i = 0 ; i <n ; i++)
    {
        idx[{x[i] , y[i]}] = i;
    }
    vector<pair<int ,int>> vv;
    for(int i = 0 ; i < n ; i++)
        vv.push_back({x[i] , y[i]});
    sort(vv.begin() , vv.end() , [](pair<int, int> a , pair<int ,int> b){return a.first + a.second < b.first + b.second;});
    u.clear();
    v.clear();
    a.clear();
    b.clear();
    taken.clear();
    for(int i = 0 ; i < n ;i++)
    {
        x[i] = vv[i].first , y[i] = vv[i].second;
    }
    DSU dsu(n);
    for(int i = 0 ; i < n ;i++)
    {
        if(idx.count({x[i] + 2 , y[i]}) && dsu.unite(idx[{x[i] , y[i]}] , idx[{x[i] + 2 , y[i]}]))
        {
            if(!taken.count({x[i] + 1 , y[i] - 1}))
            {
                u.push_back(idx[{x[i] , y[i]}]);
                v.push_back(idx[{x[i] + 2 , y[i]}]);
                a.push_back(x[i] + 1);
                b.push_back(y[i] - 1);
                taken.insert({x[i] + 1 , y[i] - 1});
            }
            else if(!taken.count({x[i] + 1 , y[i] + 1}))
            {
                u.push_back(idx[{x[i] , y[i]}]);
                v.push_back(idx[{x[i] + 2 , y[i]}]);
                a.push_back(x[i] + 1);
                b.push_back(y[i] + 1);
                taken.insert({x[i] + 1 , y[i] + 1});
            }
        }
        if(idx.count({x[i] , y[i] + 2}) && dsu.unite(idx[{x[i] , y[i]}] , idx[{x[i] , y[i] + 2}]))
        {
            
            if(!taken.count({x[i] - 1 , y[i] + 1}))
            {
                u.push_back(idx[{x[i] , y[i]}]);
                v.push_back(idx[{x[i] , y[i] + 2}]);
                b.push_back(y[i] + 1);
                a.push_back(x[i] - 1);
                taken.insert({x[i] - 1 , y[i] +1});
            }
            else if(!taken.count({x[i] + 1 , y[i] + 1}))
            {
                u.push_back(idx[{x[i] , y[i]}]);
                v.push_back(idx[{x[i] , y[i] + 2}]);
                b.push_back(y[i] + 1);
                a.push_back(x[i] + 1);
                taken.insert({x[i] + 1 , y[i] +1});
            }
        }
    }
    set<int> s;
    for(int i = 0 ;i < n ;i++)
    {
        s.insert(dsu.get(i));
    }
    if((int)s.size() == 1)
    {
        build(u , v , a , b);
        return 1;
    }
    
    return 0;
}

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