Submission #677953

#	Time	Username	Problem	Language	Result	Execution time	Memory
677953		APROHACK	Fountain Parks (IOI21_parks)	C++17	15 / 100	530 ms	46280 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
int N;
vector<pair<int, int > >node;
map<pair<int, int>, int>mp;
vector<int>u, v, a, b;
int padre[200005];

int findPadre(int k){
    if(padre[k] == k)return k;
    return padre[k] = findPadre(padre[k]);
}

void unir(int p, int q){
    p = findPadre(p);
    q = findPadre(q);
    if(p == q){
        return;
    }
    padre[p] = q;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    N = x.size();
    for(int i = 0 ; i < N ; i ++){
        node.pb({x[i], y[i]});
        mp[{x[i], y[i]}] = i;
        padre[i] = i;
    }

    queue<int>fila;
    fila.push(0);
    int current;
    while(!fila.empty()){
        current = fila.front();
        fila.pop();
        pair<int, int > derecha = {node[current].ff+2, node[current].ss}, izquierda = {node[current].ff-2, node[current].ss}, abajo = {node[current].ff, node[current].ss-2}, arriba = {node[current].ff, node[current].ss+2};
        vector<pair<int, int> >porRecorrer;
        
        porRecorrer.pb(izquierda);
        porRecorrer.pb(arriba);
        porRecorrer.pb(derecha);
        porRecorrer.pb(abajo);
        for(pair<int, int> siguiente : porRecorrer){
            if(!mp.count(siguiente))continue;
            int indxnxt = mp[siguiente];
            if(findPadre(indxnxt) == findPadre(0))continue; //(No va a pasar)
            unir(indxnxt, current);
            u.pb(current);
            v.pb(indxnxt);
            //cout << "se une " << current <<" con " << indxnxt << endl;
            fila.push(indxnxt);
        }
    }

    for(int i =0  ; i < N ; i ++){
        if(findPadre(i) != findPadre(0)){
            //cout << "padre de " <<i  << "!= padre de " << 0 << "(" << findPadre(i) << "!=" << findPadre(0) << ")" << endl;
            return 0;
        }
    }
    map<pair<int, int >, int > coordenadasUsadas;
    vector<int>mientrasA, mientrasB;
    int prioridad;
    bool seLogro = true;
    for(int i = 0 ; i < v.size() ; i++){
        if(node[v[i]].ff == node[u[i]].ff){//vertical
            pair<int, int > izquierdo = {node[v[i]].ff-1, (node[v[i]].ss+node[u[i]].ss) / 2}, derecho = {node[v[i]].ff+1, (node[v[i]].ss+node[u[i]].ss) / 2};
            if(!coordenadasUsadas.count(izquierdo)){
                mientrasA.pb(izquierdo.ff);
                mientrasB.pb(izquierdo.ss);
                //cout << " probando (" << izquierdo.ff << ", " << izquierdo.ss << ") para la union numero " << i << endl;
                coordenadasUsadas[izquierdo] = i;
            }else if(!coordenadasUsadas.count(derecho)){
                mientrasA.pb(derecho.ff);
                mientrasB.pb(derecho.ss);
                //cout << " probando (" << derecho.ff << ", " << derecho.ss << ") para la union numero " << i << endl;
                coordenadasUsadas[derecho] = i;
            }else{
                seLogro = false;
                prioridad = i;
                //cout << "Paila, reintentando desde " << prioridad;
                break;
            }
        }else{ // horizontal
            pair<int, int > arriba = {(node[v[i]].ff+node[u[i]].ff) / 2, node[v[i]].ss+1}, abajo = {(node[v[i]].ff+node[u[i]].ff) / 2, node[v[i]].ss-1};
            if(!coordenadasUsadas.count(arriba)){
                mientrasA.pb(arriba.ff);
                mientrasB.pb(arriba.ss);
                //cout << " probando (" << arriba.ff << ", " << arriba.ss << ") para la union numero " << i << endl;
                coordenadasUsadas[arriba] = i;
            }else if(!coordenadasUsadas.count(abajo)){
                mientrasA.pb(abajo.ff);
                mientrasB.pb(abajo.ss);
                //cout << " probando (" << abajo.ff << ", " << abajo.ss << ") para la union numero " << i << endl;
                coordenadasUsadas[abajo] = i;
            }else{
                seLogro = false;
                prioridad = i;
                //cout << "Paila, reintentando desde " << prioridad;
                break;
            }
        }


    }

    if(seLogro){
        build(u, v, mientrasA, mientrasB);
        return 1;
    }else{
        for(int i = 0 ; i < v.size() ; i ++){
            a.pb(0);
            b.pb(0);
        }

        coordenadasUsadas.clear();


        if(node[v[prioridad]].ff == node[u[prioridad]].ff){//vertical
            pair<int, int > izquierdo = {node[v[prioridad]].ff-1, (node[v[prioridad]].ss+node[u[prioridad]].ss) / 2}, derecho = {node[v[prioridad]].ff+1, (node[v[prioridad]].ss+node[u[prioridad]].ss) / 2};
            if(!coordenadasUsadas.count(izquierdo)){
                a[prioridad] = izquierdo.ff;
                b[prioridad] = izquierdo.ss;
                coordenadasUsadas[izquierdo] = prioridad;
            }else if(!coordenadasUsadas.count(derecho)){
                a[prioridad] = derecho.ff;
                b[prioridad] = derecho.ss;
                coordenadasUsadas[derecho] = prioridad;
            }else{
                seLogro = false;
                prioridad = prioridad;
                return 0;
            }
        }else{ // horizontal
            pair<int, int > arriba = {(node[v[prioridad]].ff+node[u[prioridad]].ff) / 2, node[v[prioridad]].ss+1}, abajo = {(node[v[prioridad]].ff+node[u[prioridad]].ff) / 2, node[v[prioridad]].ss-1};
            if(!coordenadasUsadas.count(arriba)){
                a[prioridad] = arriba.ff;
                b[prioridad] = arriba.ss;
                coordenadasUsadas[arriba] = prioridad;
            }else if(!coordenadasUsadas.count(abajo)){
                a[prioridad] = abajo.ff;
                b[prioridad] = abajo.ss;
                coordenadasUsadas[abajo] = prioridad;
            }else{
                seLogro = false;
                prioridad = prioridad;
                return 0;
            }
        }
        //cout << "en prioridad se unió en " << a[prioridad] <<", " << b[prioridad] << endl;



        for(int i = 0 ; i < v.size() ; i++){
            if(i==prioridad)continue;
            if(node[v[i]].ff == node[u[i]].ff){//vertical
                pair<int, int > izquierdo = {node[v[i]].ff-1, (node[v[i]].ss+node[u[i]].ss) / 2}, derecho = {node[v[i]].ff+1, (node[v[i]].ss+node[u[i]].ss) / 2};
                if(!coordenadasUsadas.count(izquierdo)){
                    a[prioridad] = izquierdo.ff;
                    b[prioridad] = izquierdo.ss;
                    coordenadasUsadas[izquierdo] = i;
                }else if(!coordenadasUsadas.count(derecho)){
                    a[prioridad] = derecho.ff;
                    b[prioridad] = derecho.ss;
                    coordenadasUsadas[derecho] = i;
                }else{
                    seLogro = false;
                    prioridad = i;
                    return 0;
                }
            }else{ // horizontal
                pair<int, int > arriba = {(node[v[i]].ff+node[u[i]].ff) / 2, node[v[i]].ff+1}, abajo = {(node[v[i]].ff+node[u[i]].ff) / 2, node[v[i]].ff-1};
                if(!coordenadasUsadas.count(arriba)){
                    a[prioridad] = arriba.ff;
                    b[prioridad] = arriba.ss;
                    coordenadasUsadas[arriba] = i;
                }else if(!coordenadasUsadas.count(abajo)){
                    a[prioridad] = abajo.ff;
                    b[prioridad] = abajo.ss;
                    coordenadasUsadas[abajo] = i;
                }else{
                    seLogro = false;
                    prioridad = i;
                    //cout << "Paila, no se pudo en " << i << endl;
                    return 0;
                }
            }
            //cout <<"la union " << i << "se unio en " << mientrasA.back() << ", " << mientrasB.back() << endl;


        }


        build(u, v, a, b);
        return 1;
    }

}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i = 0 ; i < v.size() ; i++){
      |                     ~~^~~~~~~~~~
parks.cpp:121:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for(int i = 0 ; i < v.size() ; i ++){
      |                         ~~^~~~~~~~~~
parks.cpp:164:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         for(int i = 0 ; i < v.size() ; i++){
      |                         ~~^~~~~~~~~~

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