Submission #1051897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051897		MarwenElarbi	Fountain Parks (IOI21_parks)	C++17	30 / 100	446 ms	48380 KiB

parks

#include <bits/stdc++.h>
using namespace std;
#include "parks.h"
#define pb push_back
#define fi first
#define se second
const int nax=2e5+5;
set<pair<int,int>> mp;
map<pair<int,int>,int> cor;
set<pair<int,int>> vis;
int parent[nax];
bool check(pair<int,int> a){
    if(!mp.count({a.fi-2,a.se})&&!mp.count({a.fi+2,a.se})&&!mp.count({a.fi,a.se-2})&&!mp.count({a.fi,a.se+2})) return false;
    return true; 
}
int find(int x){
    if(x==parent[x]) return x;
    return parent[x]=find(parent[x]);
}
bool sameset(int x,int y){
    return find(x)==find(y);
}
void joinset(int x,int y) {
    x=find(x);
    y=find(y);
    parent[x]=y;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    std::vector<int> u, v, a, b;
    int n=y.size();
    for (int i = 0; i < n; ++i) parent[i]=i;
    for (int i = 0; i < n; ++i)
    {
        mp.insert({x[i],y[i]});
        cor[{x[i],y[i]}]=i;
    }
    bool test=true;
    for(auto i:mp){
        if(!check(i)){
            test=false;
            break;
        }
        if(mp.count({i.fi+2,i.se})){
            if(sameset(cor[i],cor[{i.fi+2,i.se}])) continue;
            pair<int,int> cur={i.fi+1,i.se-1};
            if(vis.count(cur)) cur.se+=2;
            if(vis.count(cur)) continue;
            vis.insert(cur);
            joinset(cor[i],cor[{i.fi+2,i.se}]);
            a.pb(cur.fi);
            b.pb(cur.se);
            u.pb(cor[i]);
            v.pb(cor[{i.fi+2,i.se}]);
        }
        if(mp.count({i.fi,i.se+2})){
            if(sameset(cor[i],cor[{i.fi,i.se+2}])) continue;
            joinset(cor[i],cor[{i.fi,i.se+2}]);
            pair<int,int> cur={i.fi-1,i.se+1};
            if(vis.count(cur)) cur.fi+=2;
            if(vis.count(cur)) continue;
            vis.insert(cur);
            a.pb(cur.fi);
            b.pb(cur.se);
            u.pb(cor[i]);
            v.pb(cor[{i.fi,i.se+2}]);
        }
    }
    if(!test) return 0;
    if((int)u.size()!=n-1) return 0;
    build(u, v, a, b);
    return 1;
}

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