Submission #688319

#	Time	Username	Problem	Language	Result	Execution time	Memory
688319		coding_snorlax	Fountain Parks (IOI21_parks)	C++17	45 / 100	246 ms	39232 KiB

parks

#include<bits/stdc++.h>
#include "parks.h"
using namespace std;
#define mp make_pair
#define pb push_back
vector<pair<int,int>> G;
vector<pair<int,int>> x_axis[200005];
vector<pair<int,int>> y_axis[200005];
vector<pair<int,int>> choose;
vector<int> u,v,a,b;
int Boss[200005];
int query(int node){
    if(Boss[node]==node) return node;
    return Boss[node]=query(Boss[node]);
}
int Union(int x,int y){
    if(query(x)==query(y)) return 0;
    Boss[query(x)]=query(y);
    return 1;
}
int construct_roads(vector<int> x,vector<int> y){
    for(int i=0;i<200005;i++){
        Boss[i]=i;
    }
    for(int i=0;i<(int)x.size();i++){
        x_axis[x[i]].pb(mp(y[i],i));
        y_axis[y[i]].pb(mp(x[i],i));
    }
    for(int i=0;i<200005;i++){
        sort(x_axis[i].begin(),x_axis[i].end());
        sort(y_axis[i].begin(),y_axis[i].end());
    }
    //construct graph
    for(int i=0;i<200005;i++){
        for(int j=0;j<(int)x_axis[i].size()-1;j++){
            //cout<<x_axis[i][j+1].first<<"\n";
            if(x_axis[i][j+1].first-x_axis[i][j].first==2){
                G.pb(mp(x_axis[i][j+1].second,x_axis[i][j].second));
            }
        }
        for(int j=0;j<(int)y_axis[i].size()-1;j++){
            if(y_axis[i][j+1].first-y_axis[i][j].first==2){
                G.pb(mp(y_axis[i][j+1].second,y_axis[i][j].second));
            }
        }
    }
    for(auto i:G){
        //cout<<i.first<<" "<<i.second<<"\n";
        if(Union(i.first,i.second)){
            choose.pb(mp(i.first,i.second));
        }
    }
    for(auto i:choose){
        if((x[i.first]+y[i.first])%4) swap(i.first,i.second);
        //cout<<x[i.first]<<" "<<y[i.first]<<" "<<x[i.second]<<" "<<y[i.second]<<"\n";
        if(x[i.second]-x[i.first]==2){
            u.pb(i.first);v.pb(i.second);a.pb(x[i.first]+1);b.pb(y[i.first]-1);
        }
        if(x[i.second]-x[i.first]==-2){
            u.pb(i.first);v.pb(i.second);a.pb(x[i.first]-1);b.pb(y[i.first]+1);
        }
        if(y[i.second]-y[i.first]==2){
            u.pb(i.first);v.pb(i.second);a.pb(x[i.first]+1);b.pb(y[i.first]+1);
        }
        if(y[i.second]-y[i.first]==-2){
            u.pb(i.first);v.pb(i.second);a.pb(x[i.first]-1);b.pb(y[i.first]-1);
        }
        //cout<<v.back()<<" \n";
    }
    //for(int i:v) cout<<i<<" ";
    if((int)choose.size()==(int)x.size()-1){
        build(u,v,a,b);
        return 1;
    }
    return 0;

}

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