Submission #1217558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217558		hengliao	Fountain Parks (IOI21_parks)	C++20	70 / 100	915 ms	541908 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

namespace{
    const ll mxN=4e6+5;

    ll n;
    vll adj[mxN];
    ll realid[mxN];
    ll x[mxN], y[mxN];
    bool visited[mxN];
    vll v[mxN];
    vector<pll> edges;

    vector<pll> con;
    vector<pll> con2;
    vector<array<ll, 3>> con3;
    ll match[mxN];
    vll fadj[mxN];
    vll rev[mxN];
    ll cor[mxN][2];
    ll comp[mxN];
    ll timer;

    vll topo;

    ll id(pll tar){
        return lower_bound(con.begin(), con.end(), tar)-con.begin();
    }

    ll id2(pll tar){
        return lower_bound(con2.begin(), con2.end(), tar)-con2.begin();
    }

    ll id3(array<ll, 3> tar){
        return lower_bound(con3.begin(), con3.end(), tar)-con3.begin();
    }

    bool check(pll tar){
        ll tep=id(tar);
        if(tep>=(ll) con.size()) return false;
        if(con[tep].F==tar.F && con[tep].S==tar.S){
            return true;
        }
        return false;
    }

    pll lef(pll tar){
        return {tar.F-2, tar.S};
    }

    pll rig(pll tar){
        return {tar.F+2, tar.S};
    }

    pll up(pll tar){
        return {tar.F, tar.S+2};
    }

    pll down(pll tar){
        return {tar.F, tar.S-2};
    }

    void add_edge(ll u, ll v){
        adj[u].pb(v);
        adj[v].pb(u);
    }

    void dfs(ll cur){
        visited[cur]=1;
        for(auto &it:adj[cur]){
            if(!visited[it]){
                edges.pb({cur, it});
                dfs(it);
            }
        }
    }

    void add_dumb(ll u, ll v){
        if(con[u].F==con[v].F){
            con2.pb({con[u].F-1, (con[u].S+con[v].S)/2});
            con2.pb({con[u].F+1, (con[u].S+con[v].S)/2});
        }
        else{
            con2.pb({(con[u].F+con[v].F)/2, con[u].S-1});
            con2.pb({(con[u].F+con[v].F)/2, con[u].S+1});
        }
    }

    void build_edge(ll idx){
        ll uu=edges[idx].F;
        ll vv=edges[idx].S;
        if(con[uu].F==con[vv].F){
            cor[idx][0]=id2({con[uu].F-1, (con[uu].S+con[vv].S)/2});
            cor[idx][1]=id2({con[uu].F+1, (con[uu].S+con[vv].S)/2});
            con3.pb({idx, id2({con[uu].F-1, (con[uu].S+con[vv].S)/2}), 0});
            con3.pb({idx, id2({con[uu].F-1, (con[uu].S+con[vv].S)/2}), 1});
            con3.pb({idx, id2({con[uu].F+1, (con[uu].S+con[vv].S)/2}), 0});
            con3.pb({idx, id2({con[uu].F+1, (con[uu].S+con[vv].S)/2}), 1});
            v[id2({con[uu].F-1, (con[uu].S+con[vv].S)/2})].pb(idx);
            v[id2({con[uu].F+1, (con[uu].S+con[vv].S)/2})].pb(idx);
        }
        else{
            cor[idx][0]=id2({(con[uu].F+con[vv].F)/2, con[uu].S-1});
            cor[idx][1]=id2({(con[uu].F+con[vv].F)/2, con[uu].S+1});
            con3.pb({idx, id2({(con[uu].F+con[vv].F)/2, con[uu].S-1}), 0});
            con3.pb({idx, id2({(con[uu].F+con[vv].F)/2, con[uu].S-1}), 1});
            con3.pb({idx, id2({(con[uu].F+con[vv].F)/2, con[uu].S+1}), 0});
            con3.pb({idx, id2({(con[uu].F+con[vv].F)/2, con[uu].S+1}), 1});
            v[id2({(con[uu].F+con[vv].F)/2, con[uu].S-1})].pb(idx);
            v[id2({(con[uu].F+con[vv].F)/2, con[uu].S+1})].pb(idx);
        }
    }

    void add_edge2(ll xx, ll yy){
        fadj[xx].pb(yy);
        rev[yy].pb(xx);
    }

    void dfs2(ll cur){
        if(visited[cur]) return;
        visited[cur]=1;
        for(auto &it:fadj[cur]){
            dfs2(it);
        }
        topo.pb(cur);
    }

    void dfs3(ll cur){
        if(visited[cur]) return;
        visited[cur]=1;
        comp[cur]=timer;
        for(auto &it:rev[cur]){
            dfs3(it);
        }
    }
}

int construct_roads(vector<int> X, vector<int> Y) {
    memset(visited, 0, sizeof(visited));
    if (X.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    n=X.size();
    for(ll i=0;i<n;i++){
        x[i]=X[i];
        y[i]=Y[i];
    }
    for(ll i=0;i<n;i++){
        con.pb({x[i], y[i]});
    }
    sort(con.begin(), con.end());
    con.erase(unique(con.begin(), con.end()), con.end());
    for(ll i=0;i<n;i++){
        ll cnt=0;
        if(check(up(con[i]))){
            cnt++;
            add_edge(i, id(up(con[i])));
        }
        if(check(down(con[i]))){
            cnt++;
            add_edge(i, id(down(con[i])));
        }
        if(cnt<2){
            if(check(lef(con[i]))){
                add_edge(i, id(lef(con[i])));
            }
            if(check(rig(con[i]))){
                cnt++;
                add_edge(i, id(rig(con[i])));
            }
        }
    }
    dfs(0);
    if((ll) edges.size()<n-1) return 0;
    for(auto &[xx, yy]:edges){
        // cout<<con[xx].F<<' '<<con[xx].S<<"  "<<con[yy].F<<' '<<con[yy].S<<'\n';
        add_dumb(xx, yy);
    }

    sort(con2.begin(), con2.end());
    con2.erase(unique(con2.begin(), con2.end()), con2.end());
    // for(auto &[xx, yy]:con2){
    //     cout<<xx<<' '<<yy<<'\n';
    // }

    for(ll i=0;i<n-1;i++){
        build_edge(i);
    }

    sort(con3.begin(), con3.end());
    con3.erase(unique(con3.begin(), con3.end()), con3.end());

    for(ll i=0;i<n-1;i++){
        ll tep1=id3({i, cor[i][0], 0});
        ll tep2=id3({i, cor[i][0], 1});
        ll tep3=id3({i, cor[i][1], 0});
        ll tep4=id3({i, cor[i][1], 1});
        add_edge2(tep1, tep4);
        add_edge2(tep3, tep2);
        add_edge2(tep2, tep3);
        add_edge2(tep4, tep1);
    }

    for(ll i=0;i<(ll) con2.size();i++){
        if((ll) v[i].size()==2){
            ll tep1=id3({v[i][0], i, 0});
            ll tep2=id3({v[i][0], i, 1});
            ll tep3=id3({v[i][1], i, 0});
            ll tep4=id3({v[i][1], i, 1});
            add_edge2(tep2, tep3);
            add_edge2(tep4, tep1);
        }
        else if((ll) v[i].size()==3){
            ll tep1=id3({v[i][0], i, 0});
            ll tep2=id3({v[i][0], i, 1});
            ll tep3=id3({v[i][1], i, 0});
            ll tep4=id3({v[i][1], i, 1});
            ll tep5=id3({v[i][2], i, 0});
            ll tep6=id3({v[i][2], i, 1});
            add_edge2(tep2, tep3);
            add_edge2(tep2, tep5);
            add_edge2(tep4, tep1);
            add_edge2(tep4, tep5);
            add_edge2(tep6, tep1);
            add_edge2(tep6, tep3);
        }
    }

    ll siz=con3.size();

    memset(visited, 0, sizeof(visited));

    for(ll i=0;i<siz;i++){
        dfs2(i);
    }

    reverse(topo.begin(), topo.end());
    memset(visited, 0, sizeof(visited));
    timer=0;

    for(auto &it:topo){
        if(!visited[it]){
            dfs3(it);
            timer++;
        }
    }

    // for(ll i=0;i<n-1;i++){
    //     ll tep1=id3({i, cor[i][0], 0});
    //     ll tep2=id3({i, cor[i][0], 1});
    //     ll tep3=id3({i, cor[i][1], 0});
    //     ll tep4=id3({i, cor[i][1], 1});
    //     if(comp[tep1]<comp[tep2]){
    //         cout<<"built:\n";
    //         cout<<con[edges[i].F].F<<' '<<con[edges[i].F].S<<"  "
    //         <<con[edges[i].S].F<<' '<<con[edges[i].S].S<<"  "<<
    //         con2[cor[i][0]].F<<' '<<con2[cor[i][0]].S<<'\n';
    //     }
    //     else{
    //         cout<<"built:\n";
    //         cout<<con[edges[i].F].F<<' '<<con[edges[i].F].S<<"  "
    //         <<con[edges[i].S].F<<' '<<con[edges[i].S].S<<"  "<<
    //         con2[cor[i][1]].F<<' '<<con2[cor[i][1]].S<<'\n';
    //     }
    // }

    vector<vector<int>> re(4, vector<int>(n-1));

    for(ll i=0;i<n;i++){
        realid[id({x[i], y[i]})]=i;
    }

    for(ll i=0;i<n-1;i++){
        re[0][i]=realid[edges[i].F];
        re[1][i]=realid[edges[i].S];
        ll tep1=id3({i, cor[i][0], 0});
        ll tep2=id3({i, cor[i][0], 1});
        ll tep3=id3({i, cor[i][1], 0});
        ll tep4=id3({i, cor[i][1], 1});
        if(comp[tep1]<comp[tep2]){
            re[2][i]=con2[cor[i][0]].F;
            re[3][i]=con2[cor[i][0]].S;
        }
        else{
            re[2][i]=con2[cor[i][1]].F;
            re[3][i]=con2[cor[i][1]].S;
        }
    }

    build(re[0], re[1], re[2], re[3]);

    return 1;
}

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