Submission #1050869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050869		amine_aroua	Fountain Parks (IOI21_parks)	C++17	30 / 100	307 ms	63180 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<bool> vis;
void dfs(int i)
{
    if(vis[i])
        return;
    vis[i] = 1;
    for(auto j : adj[i])
    {
        dfs(j);
    }
}
void add_edge(int u , int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}
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();
    adj.assign(n , {});
    vis.assign(n , 0);
    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());
    int cnt = 1;
    while(cnt--)
    {
        u.clear();
        v.clear();
        a.clear();
        b.clear();
        taken.clear();
        adj.assign(n , {});
        vis.assign(n ,0);

        for(int i = 0 ; i < n ;i++)
        {
            x[i] = vv[i].first , y[i] = vv[i].second;
        }
        bool acc = 1;
        for(int i = 0 ; i < n ;i++)
        {
            if(idx.count({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}))
            {
                
                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});
                }
            }
        }
        for(int i = 0 ; i < (int)u.size() ; i++)
        {
            add_edge(u[i] , v[i]);
        }
        dfs(0);
        for(int i = 0 ; i < n ; i++)
        {
            if(!vis[i])
            {
                acc = 0;
                break;
            }
        }
        if(!acc)
            continue;
        build(u , v , a , b);
        return 1;
    }
    return 0;
}

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