Submission #995081

#	Time	Username	Problem	Language	Result	Execution time	Memory
995081		dimashhh	Fountain Parks (IOI21_parks)	C++17	100 / 100	353 ms	41516 KiB

parks

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

using namespace std;

const int N = 1e6 + 1;
vector<array<int,3>> a;
vector<pair<int,int>> edges;
vector<int> u,v,x,y;
int n,p[N];
map<pair<int,int>,int> id;
int get(int v){
    if(p[v] == v) return v;
    return p[v] = get(p[v]);
}
bool merge(int x,int y){
    x = get(x);
    y = get(y);
    if(x == y) return false;
    p[x] = y;
    return true;
}
bool check(){
    for(int i = 1;i < n;i++){
        if(get(i) != get(0)) return false;
    }
    return true;
}
int P[N],timer = 1;
map<pair<int,int>,pair<int,int>> mt;
map<pair<int,int>,int> vis;
vector<int> xx,yy;
bool dfs(pair<int,int> C){
    int i =C.first,j= C.second;
    if(vis[{i,j}] == timer) return false;
    vis[{i,j}] = timer;
    if(yy[i] == yy[j]){
        if(!mt.count({xx[i] - 1,yy[i] - 1}) || dfs(mt[{xx[i] - 1,yy[i] - 1}])){
            mt[{xx[i] - 1,yy[i] - 1}] = C;
            return true;
        }
        if(!mt.count({xx[i] - 1,yy[i] + 1}) || dfs(mt[{xx[i] - 1,yy[i] + 1}])){
            mt[{xx[i] - 1,yy[i] + 1}] = C;
            return true;
        }
    }else{
        if(!mt.count({xx[i] - 1,yy[i] - 1}) || dfs(mt[{xx[i] - 1,yy[i] - 1}])){
            mt[{xx[i] - 1,yy[i] - 1}] = C;
            return true;
        }
        if(!mt.count({xx[i] + 1,yy[i] - 1}) || dfs(mt[{xx[i] + 1,yy[i] - 1}])){
            mt[{xx[i] + 1,yy[i] - 1}] = C;
            return true;
        }
    }
    return false;
}
bool vis1[N];
int construct_roads(std::vector<int> X, std::vector<int> Y){
    xx = X;
    yy = Y;
    n = (int)X.size();
    for(int i = 0;i < n;i++){
        p[i] = id[{X[i],Y[i]}] = i;
        P[i] = i;
    }
    sort(P,P + n,[&](int c,int d){
        return make_pair(X[c],Y[c]) < make_pair(X[d],Y[d]);
    });
    for(int j = 0;j < n;j++){
        int i = P[j];
        if(id.count({X[i] - 2,Y[i]})){
            merge(i,id[{X[i] - 2,Y[i]}]);
            edges.push_back({i,id[{X[i] - 2,Y[i]}]});
        }
        if(id.count({X[i],Y[i] - 2})){
            merge(i,id[{X[i],Y[i] - 2}]);
            edges.push_back({i,id[{X[i],Y[i] - 2}]});
        }
    }
    if(!check()) return 0;
    for(int i =0 ;i < n;i++){
        p[i] =i;
    }
    id.clear();
    for(int f =0 ;f < (int)edges.size();f++){
        int i = edges[f].first,j = edges[f].second;
        if(get(i) == get(j)) continue;
        if(X[i] == X[j]){
            if(!mt.count({X[i] - 1,Y[i] - 1})){
                mt[{X[i] - 1,Y[i] - 1}] = {i,j};
                vis1[f] = 1;
            }else if(!mt.count({X[i] + 1,Y[i] - 1})){
                mt[{X[i] + 1,Y[i] - 1}] = {i,j};
                vis1[f] = 1;
            }
        }else{
            if(!mt.count({X[i] - 1,Y[i] - 1})){
                mt[{X[i] - 1,Y[i] - 1}] = {i,j};
                vis1[f] = 1;
            }else if(!mt.count({X[i] - 1,Y[i] + 1})){
                mt[{X[i] - 1,Y[i] + 1}] = {i,j};
                vis1[f] = 1;
            }
        }
        if(vis1[f]){
            merge(i,j);
        }
    }
    for(int i = 0;i < (int)edges.size();++i){
        if(vis1[i] ||get(edges[i].first) == get(edges[i].second)) continue;
        timer++;
        bool ok = dfs({edges[i].first,edges[i].second});
        if(ok){
            merge(edges[i].first,edges[i].second);
        }
    }
    for(auto [pp,pp1]:mt){
        x.push_back(pp.first);y.push_back(pp.second);
        u.push_back(pp1.first);v.push_back(pp1.second);
    }
    if(!check()) return 0;
    build(u,v,x,y);
    return 1;
}

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