Submission #813565

#	Time	Username	Problem	Language	Result	Execution time	Memory
813565		Ozy	Fountain Parks (IOI21_parks)	C++17	5 / 100	816 ms	73056 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++) 
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 200000
//para los pares en general
#define xx first
#define yy second

lli n,a,b,uf[MAX+2],uniones;
lli s[2] = {-1,1};
map<pll,lli> mapa,a_vis,b_vis;
lli dir[8] = {0,-2,0,2,2,0,-2,0};
vector<pll> aristas;
vector<int> u,v,b_x,b_y;

lli sube(lli pos) {
    if (uf[pos] == pos) return pos;
    uf[pos] = sube(uf[pos]);
    return uf[pos];
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    
    n = x.size();
    rep(i,0,n-1) {
        uf[i] = i;
        
        mapa[{x[i],y[i]}] = i;
        rep(j,0,3) {
            a = x[i] + dir[j];
            b = y[i] + dir[j+4];
            if(mapa.find({a,b}) != mapa.end()) {
                aristas.push_back({i,mapa[{a,b}]});
                a = sube(mapa[{a,b}]);
                b = sube(i);

                if (a != b) {
                    uniones++;
                    uf[a] = b;
                }
            }
        }

    }

    if(uniones != n-1) return 0;

    for (auto act : aristas) {
        //debugsl(act.first);
        //debug(act.second);

        while (a_vis.find(act) == a_vis.end()) {
            a_vis[act] = 1;
            swap(act.first,act.second);
            a_vis[act] = 1;

            //opciones para colocar la banca
            pll w = {(x[act.first] + x[act.second])/2, (y[act.first] + y[act.second])/2};
            pll z = {(x[act.first] + x[act.second])/2, (y[act.first] + y[act.second])/2};
            if (x[act.first] == x[act.second]) {
                w.xx++;
                z.xx--;
            }
            else {
                w.yy++;
                z.yy--;
            }

            if (b_vis.find(w) == mapa.end()) { //pongo mi banca en w
                b_vis[w] = 1;

                b_x.push_back(w.xx);
                b_y.push_back(w.yy);
                u.push_back(act.first);
                v.push_back(act.second);
            }
            else {
                b_vis[z] = 1;

                b_x.push_back(z.xx);
                b_y.push_back(z.yy);
                u.push_back(act.first);
                v.push_back(act.second);

                w = z;   
            }

            //busco si es que el esta en una tripleta y continuo la busqueda
            rep(i,0,1) {
                rep(j,0,1) {
                    z.xx = w.xx + s[i];
                    z.yy = w.yy + s[j];

                    if (z.xx == x[act.first] && z.yy == y[act.first]) continue;
                    if (z.xx == x[act.second] && z.yy == y[act.second]) continue;
                    if (mapa.find(z) == mapa.end()) continue;

                    if (z.xx == x[act.first] || z.yy == y[act.first]) act.second = mapa[z];
                    else act.first = mapa[z];
                }
            }

        }
        
    }

    build(u,v,b_x,b_y);
    return 1;
}

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