Submission #795749

#	Time	Username	Problem	Language	Result	Execution time	Memory
795749		Khizri	Fountain Parks (IOI21_parks)	C++17	5 / 100	1576 ms	81284 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5;
int n,x[mxn],y[mxn],p[mxn],sz[mxn];
int ax[4]={1,1,-1,-1};
int ay[4]={-1,1,1,-1};
vector<pii>vt;
map<pii,int>mp;
int fnd(int u){
    if(p[u]==u) return u;
    return p[u]=fnd(p[u]);
}
void Union(int u,int v){
    u=fnd(u);
    v=fnd(v);
    if(u!=v){
        if(sz[u]>sz[v]) swap(u,v);
        sz[u]+=sz[v];
        p[v]=u;
    }
}
int construct_roads(vector<int> xx, vector<int> yy) {
    n=xx.size();
    if(n==1){
        build({},{},{},{});
        return 1;
    }
    for(int i=0;i<n;i++){
        vt.pb({xx[i],yy[i]});
        mp[{xx[i],yy[i]}]=i+1;
        x[i+1]=xx[i];
        y[i+1]=yy[i];
    }
    //for(int i=1;i<=n;i++){
        //if(!mp[{x[i],y[i]+2}]&&!mp[{x[i],y[i]-2}]&&!mp[{x[i]+2,y[i]}]&&!mp[{x[i]-2,y[i]}]) return 0;
    //}
    sort(all(vt));
    //for(int i=1;i<n;i++){
        //if(abs(vt[i].F-vt[i-1].F)>2||abs(vt[i].S-vt[i-1].S)>2) return 0;
    //}
    set<pii>st;
    for(int i=1;i<=n;i++){
        st.insert({x[i]-1,y[i]-1});
        st.insert({x[i]+1,y[i]-1});
        st.insert({x[i]-1,y[i]+1});
        st.insert({x[i]+1,y[i]+1});
    }
    for(int i=1;i<=n;i++){
        p[i]=i;
        sz[i]=1;
    }
    vector<int>idxl,idxr,posl,posr;
    int cnt=n-1;
    int say=4;
    while(cnt&&say--){
        for(auto it=st.begin();it!=st.end();it++){
            int l=it->F;
            int r=it->S;
            set<int>dif;
            vector<int>idx;
            //cout<<"OK"<<endl;
            for(int i=0;i<4;i++){
                int u=l+ax[i],v=r+ay[i];
                int node=mp[{u,v}];
                if(node>0&&!dif.count(fnd(node))){
                    dif.insert(fnd(node));
                    idx.pb(node);
                }
            }
            //cout<<dif.size()<<endl;
            if(dif.size()==1||dif.size()>2) continue;
            idxl.pb(idx[0]-1);
            idxr.pb(idx[1]-1);
            //cout<<idx[0]<<' '<<idx[1]<<endl;
            posl.pb(l);
            posr.pb(r);
            Union(idx[0],idx[1]);
            cnt--;
        }
        //cnt--;
    }
    say=4;
    while(cnt&&say--){
        for(auto it=st.begin();it!=st.end();it++){
            int l=it->F;
            int r=it->S;
            set<int>dif;
            vector<int>idx;
            //cout<<"OK"<<endl;
            for(int i=0;i<4;i++){
                int u=l+ax[i],v=r+ay[i];
                int node=mp[{u,v}];
                if(node>0&&!dif.count(fnd(node))){
                    dif.insert(fnd(node));
                    idx.pb(node);
                }
            }
            //cout<<dif.size()<<endl;
            if(dif.size()==1) continue;
            idxl.pb(idx[0]-1);
            idxr.pb(idx[1]-1);
            //cout<<idx[0]<<' '<<idx[1]<<endl;
            posl.pb(l);
            posr.pb(r);
            Union(idx[0],idx[1]);
            cnt--;
        }
        //cnt--;
    }
    if(cnt) return 0;
    build(idxl,idxr,posl,posr);
    return 1;
}
/*
5
4 4 
4 6 
6 4
4 2
2 4
*/

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