Submission #831908

#	Time	Username	Problem	Language	Result	Execution time	Memory
831908		arsijo	Fountain Parks (IOI21_parks)	C++17	45 / 100	369 ms	39004 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> cons[200001];
int mask_l[200001];
vector<int> u;
vector<int> v;
vector<int> a;
vector<int> b;
struct dsu{
    int sz = 0;
    vector<int> pr;
    int p(int v){
        if(pr[v] == v) return v;
        return pr[v] = p(pr[v]);
    }
    bool un(int u,int v){
        u = p(u);
        v = p(v);
        if(u == v){
            return 0;
            exit(1);
        }
        pr[u] = v;
        sz++;
        return 1;
    }
} D;
int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    D.pr.resize(n);
    map<pair<int,int>,int> sol;
    for (int i = 0; i < n; ++i)
    {
        D.pr[i] = i;
    }
    vector<pair<int,pair<int,int>>> x_d;
    vector<pair<int,pair<int,int>>> y_d;
    for (int i = 0; i < n; ++i)
    {
        x_d.push_back({x[i],{y[i],i}});
        y_d.push_back({y[i],{x[i],i}});
        sol[{x[i],y[i]}] = i;
    }
    sort(x_d.begin(), x_d.end());
    sort(y_d.begin(), y_d.end());
    for (int i = 1; i < n; ++i)
    {
        if(x_d[i].first == x_d[i-1].first and x_d[i].second.first-2 == x_d[i-1].second.first){
            D.un(x_d[i-1].second.second,x_d[i].second.second);
        }
    }
    for (int i = 1; i < n; ++i)
    {
        if(y_d[i].first == y_d[i-1].first and y_d[i].second.first-2 == y_d[i-1].second.first){
            D.un(y_d[i-1].second.second,y_d[i].second.second);
        }
    }
    if(D.sz != n-1) return 0;
    for(int i = 0;i < n;i++){
        //assert(sol.count({x[i],y[i]}) + sol.count({x[i]+2,y[i]})+sol.count({x[i]+2,y[i]+2})+sol.count({x[i],y[i]+2}) < 4);
    }
    for (int i = 0; i < n; ++i)
    {
        if(sol.count({x[i],y[i]+2})){
            u.push_back(sol[{x[i],y[i]+2}]);
            v.push_back(i);
            if((x[i]+y[i])&3) a.push_back(x[i]+1);
            else a.push_back(x[i]-1);
            b.push_back(y[i]+1);
        }

        if(sol.count({x[i]+2,y[i]})){
            u.push_back(sol[{x[i]+2,y[i]}]);
            v.push_back(i);
            if((x[i]+y[i])&3) b.push_back(y[i]-1);
            else b.push_back(y[i]+1);
            a.push_back(x[i]+1);
        }
    }
    //if(points.size() != n-1) return 0;
    build(u,v,a,b);
    return 1;
}

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