Submission #818040

#	Time	Username	Problem	Language	Result	Execution time	Memory
818040		alvingogo	Fountain Parks (IOI21_parks)	C++17	100 / 100	867 ms	72116 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct DSU{
    vector<int> bo,ss;
    void init(int x){
        bo.resize(x);
        ss.resize(x,1);
        iota(bo.begin(),bo.end(),0);
    }  
    int find(int x){
        return bo[x]==x?x:bo[x]=find(bo[x]);
    }
    int merge(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y){
            return 0;
        }
        bo[x]=y;
        ss[y]+=ss[x];
        return 1;
    }
}dsu;

vector<int> au,av,aa,ab;
set<pair<int,int> > vis;
void ag(int a,int b,int c,int d){
    au.push_back(a);
    av.push_back(b);
    dsu.merge(a,b);
    aa.push_back(c);
    ab.push_back(d);
    vis.insert({c,d});
}
int construct_roads(vector<int> x, vector<int> y) {
    vis.clear();
    if (x.size() == 1) {
	    build({}, {}, {}, {});
        return 1;
    }
    map<pair<int,int>,int> mp;
    int n=x.size();
    for(int i=0;i<n;i++){
        mp[{x[i],y[i]}]=i;
    }
    dsu.init(n);
    const int dx[4]={0,0,2,-2},dy[4]={2,-2,0,0};
    function<void(pair<int,int>,int)> dfs=[&](pair<int,int> w,int q){
        int a=0,b=0,c=0,d=0;
        if(dx[q]){
            a=b=dx[q]/2;
            c=1;
            d=-1;
        }
        else{
            a=1;
            b=-1;
            c=d=dy[q]/2;
        }
        int e=0,f=0,g=0,h=0;
        int way=2*(1-q/2);
        if(mp.find({w.fs+a,w.sc+c})==mp.end()){
            if(mp.find({w.fs+b,w.sc+d})==mp.end()){
                return;
            }
            way++;
        }
        if(dx[way]){
            e=f=dx[way]/2;
            g=1;
            h=-1;
        }
        else{
            e=1;
            f=-1;
            g=h=dy[way]/2;
        }
        for(int i=w.fs,j=w.sc;;i+=dx[way],j+=dy[way]){
            int sx=i+e,sy=j+g,tx=i+f,ty=j+h;
            if(mp.find({sx,sy})==mp.end() || mp.find({tx,ty})==mp.end()){
                
                if(way<2){
                    if(vis.find({i,j})!=vis.end()){
                        break;
                    }
                    ag(mp[{sx-dx[way],sy-dy[way]}],mp[{tx-dx[way],ty-dy[way]}],i,j);
                }
                dfs({i,j},way);
                break;
            }
            else{
                if(way>=2){
                    if(vis.find({i+dx[way],j+dy[way]})!=vis.end()){
                        break;
                    }
                    ag(mp[{sx,sy}],mp[{tx,ty}],i+dx[way],j+dy[way]);
                }
            }
        }
    };
    for(int p=0;p<n;p++){
        int c=x[p]+2,d=y[p];
        if(mp.find({c,d})!=mp.end()){
            int a=mp[{c,d}];
            if(vis.find({x[p]+1,y[p]+1})==vis.end() && !(mp.find({x[p]+2,y[p]+2})!=mp.end() && mp.find({x[p],y[p]+2})!=mp.end())){
                ag(a,p,x[p]+1,y[p]+1);
                dfs({x[p]+1,y[p]+1},0);
            }
            else if(vis.find({x[p]+1,y[p]-1})==vis.end() && !(mp.find({x[p]+2,y[p]-2})!=mp.end() && mp.find({x[p],y[p]-2})!=mp.end())){
                ag(a,p,x[p]+1,y[p]-1);
                dfs({x[p]+1,y[p]-1},1);
            }
        }
    }
    for(int p=0;p<n;p++){
        int c=x[p],d=y[p]+2;
        if(mp.find({c,d})!=mp.end()){
            int a=mp[{c,d}];
            if(vis.find({x[p]+1,y[p]+1})==vis.end()){
                ag(a,p,x[p]+1,y[p]+1);
            }
            else if(vis.find({x[p]-1,y[p]+1})==vis.end()){
                ag(a,p,x[p]-1,y[p]+1);
            }
        }
    }
    if(dsu.ss[dsu.find(0)]!=n){
        return 0;
    }
    build(au,av,aa,ab);
    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