Submission #828890

#	Time	Username	Problem	Language	Result	Execution time	Memory
828890		fatemetmhr	Fountain Parks (IOI21_parks)	C++17	55 / 100	850 ms	104156 KiB

parks

// Be Name Khoda //

//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

#include "parks.h"
#include <bits/stdc++.h>

using namespace std;


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


typedef long long ll;

#define debug(x)  cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)    x.begin(), x.end()
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define fi        first
#define se        second
#define pb        push_back
#define mp        make_pair

const int maxn5 = 1e6 + 10;


int n, q[maxn5], cnt[maxn5], ti, par[maxn5];
bool mark[maxn5];
vector <int> ret[2], ed[2], edg[maxn5];
vector <pair<int, int>> ver, toadd;
pair<pair <int, int>, pair<int, int>> adj[maxn5];
map <pair<int, int>, int> av, num;

bool bad(int i, int j, int x, int y){
    if(i == x){
        return (num[mp(i - 1, (j + y) / 2)] > 0 || num[mp(i + 1, (j + y) / 2)] > 0);
    }
    return (num[mp((i + x) / 2, j - 1)] > 0 || num[mp((i + x) / 2, j + 1)] > 0);
}

void dfs0(int v, int x, int y){
    par[v] = ti;
    av.erase(mp(x, y));
    if(av.find(mp(x - 2, y)) != av.end() && !bad(x, y, x - 2, y)){
        int u = av[mp(x - 2, y)];
        ed[0].pb(v);
        ed[1].pb(u);
        num[mp(x - 1, y - 1)]++;
        num[mp(x - 1, y + 1)]++;
        dfs0(u, x - 2, y);
    }
    else if(av.find(mp(x - 2, y)) != av.end())
        toadd.pb(mp(v, av[mp(x - 2, y)]));
    if(av.find(mp(x + 2, y)) != av.end() && !bad(x, y, x + 2, y)){
        int u = av[mp(x + 2, y)];
        ed[0].pb(v);
        ed[1].pb(u);
        num[mp(x + 1, y - 1)]++;
        num[mp(x + 1, y + 1)]++;
        dfs0(u, x + 2, y);
    }
    else if(av.find(mp(x + 2, y)) != av.end())
        toadd.pb(mp(v, av[mp(x + 2, y)]));
    if(av.find(mp(x, y - 2)) != av.end() && !bad(x, y, x, y - 2)){
        int u = av[mp(x, y - 2)];
        ed[0].pb(v);
        ed[1].pb(u);
        num[mp(x - 1, y - 1)]++;
        num[mp(x + 1, y - 1)]++;
        dfs0(u, x, y - 2);
    }
    else if(av.find(mp(x, y - 2)) != av.end())
        toadd.pb(mp(v, av[mp(x, y - 2)]));
    if(av.find(mp(x, y + 2)) != av.end() && !bad(x, y, x, y + 2)){
        int u = av[mp(x, y + 2)];
        ed[0].pb(v);
        ed[1].pb(u);
        num[mp(x - 1, y + 1)]++;
        num[mp(x + 1, y + 1)]++;
        dfs0(u, x, y + 2);
    }
    else if(av.find(mp(x, y + 2)) != av.end())
        toadd.pb(mp(v, av[mp(x, y + 2)]));
}

void dfs2(int v){
    mark[v] = true;
    for(auto u : edg[v]) if(!mark[u]){
        mark[u] = true;
        //debug(v);
        //debug(u);
        ret[0][v] = ver[u - (n - 1)].fi;
        ret[1][v] = ver[u - (n - 1)].se;
        for(auto z : edg[u]) if(!mark[z])
            dfs2(z);
        return;
    }
}

int get_par(int a){return par[a] == -1 ? a : par[a] = get_par(par[a]);}


int construct_roads(std::vector<int> x, std::vector<int> y) {
    n = x.size();
    for(int i = 0; i < n; i++){
        av[mp(x[i], y[i])] = i;
    }
    for(int i = 0; i < n; i++) if(av.find(mp(x[i], y[i])) != av.end()){
        ti = i;
        dfs0(i, x[i], y[i]);
        par[i] = -1;
    }
    shuffle(all(toadd), rng);
    for(auto [u, v] : toadd){
        int a = get_par(u);
        int b = get_par(v);
        if(a == b)
            continue;
        ed[0].pb(u);
        ed[1].pb(v);
        par[a] = b;
    }
    if(int(ed[0].size()) < n - 1)
        return 0;

    for(int i = 0; i < n - 1; i++){
        if(x[ed[0][i]] == x[ed[1][i]]){
            adj[i].fi = mp(x[ed[0][i]] - 1, (y[ed[0][i]] + y[ed[1][i]]) / 2);
            adj[i].se = mp(x[ed[0][i]] + 1, (y[ed[0][i]] + y[ed[1][i]]) / 2);
        }
        else{
            adj[i].fi = mp((x[ed[0][i]] + x[ed[1][i]]) / 2, y[ed[0][i]] - 1);
            adj[i].se = mp((x[ed[0][i]] + x[ed[1][i]]) / 2, y[ed[0][i]] + 1);
        }
        ver.pb(adj[i].fi);
        ver.pb(adj[i].se);
    }
    sort(all(ver));
    ver.resize(unique(all(ver)) - ver.begin());
    for(int i = 0; i < n - 1; i++){
        int pt = lower_bound(all(ver), adj[i].fi) - ver.begin();
        edg[i].pb(pt + n - 1);
        pt = lower_bound(all(ver), adj[i].se) - ver.begin();
        edg[i].pb(pt + n - 1);
        edg[edg[i][0]].pb(i);
        edg[edg[i][1]].pb(i);
        cnt[edg[i][0]]++;
        cnt[edg[i][1]]++;
    }
    /*
    for(int i = 0; i < int(ver.size()) + n - 1; i++){
        //debug(i);
        for(auto u : edg[i])
            cout << u << ' ';
        cout << endl;
    }
    //*/
    int l = 0, r = 0;
    for(int i = 0; i < int(ver.size()); i++) if(edg[i + n - 1].size() == 1){
        q[r++] = i + n - 1;
        mark[i + n - 1] = true;
    }
    ret[0].resize(n - 1);
    ret[1].resize(n - 1);
    //debug(r);
    while(l < r){
        int v = q[l++];
        for(auto u : edg[v]) if(!mark[u]){
            mark[u] = true;
            //debug(v);
            //debug(u);
            for(auto z : edg[u]){
                cnt[z]--;
                if(!mark[z] && cnt[z] == 1){
                    q[r++] = z;
                    mark[z] = true;
                }
            }
            ret[0][u] = ver[v - (n - 1)].fi;
            ret[1][u] = ver[v - (n - 1)].se;
        }
    }
    //return 0;
    //cout << ed[0].size() << ' ' << ed[1].size() << ' ' << ret[0].size() << ' ' << ret[1].size() << endl;
    for(int i = 0; i < n - 1; i++) if(!mark[i])
        dfs2(i);
    build(ed[0], ed[1], ret[0], ret[1]);
    return 1;
}

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