Submission #896381

#	Time	Username	Problem	Language	Result	Execution time	Memory
896381		abcvuitunggio	Fountain Parks (IOI21_parks)	C++17	100 / 100	353 ms	53764 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int n,p[200001],s[200001],cnt;
map <int, int> mp[300001];
vector <int> order;
int f(int i){
    return (p[i]==i?i:p[i]=f(p[i]));
}
bool unite(int i, int j){
    i=f(i);
    j=f(j);
    if (i==j)
        return false;
    p[j]=i;
    return true;
}
int construct_roads(vector <int> x, vector <int> y){
    vector <int32_t> u,v,a,b;
    n=x.size();
    for (int i=0;i<n;i++){
        mp[x[i]][y[i]]=i;
        order.push_back(i);
        s[i]=x[i]+y[i];
    }
    iota(p,p+n,0);
    sort(order.begin(),order.end(),[](int i, int j){return s[i]<s[j];});
    for (int i:order){
        if (mp[x[i]].count(y[i]-2)){
            int j=mp[x[i]][y[i]-2],X=x[i]+(x[i]+y[i])%4-1,Y=y[i]-1;
            if (!mp[X].count(Y)){
                u.push_back(i);
                v.push_back(j);
                cnt+=unite(i,j);
                a.push_back(X);
                b.push_back(Y);
                mp[X][Y]=1;
            }
        }
        if (mp[x[i]-2].count(y[i])){
            int j=mp[x[i]-2][y[i]],X=x[i]-1,Y=y[i]+1-(x[i]+y[i])%4;
            if (!mp[X].count(Y)){
                u.push_back(i);
                v.push_back(j);
                cnt+=unite(i,j);
                a.push_back(X);
                b.push_back(Y);
                mp[X][Y]=1;
            }
        }
    }
    if (cnt<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: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30