Submission #814292

#	Time	Username	Problem	Language	Result	Execution time	Memory
814292		alvingogo	Fountain Parks (IOI21_parks)	C++17	45 / 100	1414 ms	113088 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;
void ag(int a,int b,int c,int d){
    au.push_back(a);
    av.push_back(b);
    aa.push_back(c);
    ab.push_back(d);
}
map<pair<int,int>,int> pt,cn;
vector<pair<int,int> > tl;
vector<vector<int> > eg;
vector<int> se,vis;
int cnt=0;
void add(pair<int,int> a,pair<int,int> x){
    if(a.fs>a.sc){
        swap(a.fs,a.sc);
    }
    if(cn.find(a)==cn.end()){
        cn[a]=cnt;
        cnt++;
        eg.push_back(vector<int>());
        tl.push_back(a);
        se.push_back(0);
    }
    if(pt.find(x)==pt.end()){
        pt[x]=cnt;
        cnt++;
        eg.push_back(vector<int>());
        tl.push_back(x);
        se.push_back(1);
    }
    //cout << cn[a] << " " << pt[x] << "\n";
    eg[cn[a]].push_back(pt[x]);
    eg[pt[x]].push_back(cn[a]);
}
void dfs(int r){
    vis[r]=1;
    int p=0;
    for(auto h:eg[r]){
        if(vis[h]==0){
            vis[h]=1;
            p=h;
            ag(tl[r].fs,tl[r].sc,tl[h].fs,tl[h].sc);
            break;
        }
    }
    for(auto h:eg[p]){
        if(vis[h]==0){
            dfs(h);
            break;
        }
    }
}
int construct_roads(vector<int> x, vector<int> y) {
    cn.clear();
    pt.clear();
    eg.clear();
    se.clear();
    tl.clear();
    vis.clear();
    cnt=0;
    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};
    for(int p=0;p<n;p++){
        for(int k=0;k<4;k++){
            int c=x[p]+dx[k],d=y[p]+dy[k];
            if(mp.find({c,d})!=mp.end()){
                int a=mp[{c,d}];
                if(dsu.merge(a,p)){
                    if(x[a]==x[p]){
                        int u=(y[a]+y[p])/2;
                        add({a,p},{x[a]-1,u});
                        add({a,p},{x[a]+1,u});
                    }
                    else{
                        int u=(x[a]+x[p])/2;
                        add({a,p},{u,y[a]-1});
                        add({a,p},{u,y[a]+1});
                    }
                }
            }
        }
    }
    if(dsu.ss[dsu.find(0)]!=n){
        return 0;
    }
    vis.resize(cnt);
    for(int i=0;i<cnt;i++){
        if(se[i]==0 && !vis[i]){
            dfs(i);
        }
    }
    build(au,av,aa,ab);
    return 1;
}

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