Submission #1178323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178323		PagodePaiva	Fountain Parks (IOI21_parks)	C++20	70 / 100	909 ms	193348 KiB

parks

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

using namespace std;

const int N = 600010;
vector <int> g[N];
vector <pair <int, int>> x[N];
vector <pair <int, int>> y[N];
map <pair <int, int>, int> mapear[2];
array <int, 4> pontos[4*N];
vector <pair <int, int>> arvore;
vector <pair <int, int>> arestas;
int mark[N];
int tamanho_componente;

void dfs(int v){
    mark[v] = 1;
    tamanho_componente++;
    for(auto x : g[v]){
        if(mark[x]) continue;
        arvore.push_back({x, v});
        dfs(x);
    }
    return;
}

vector <pair <int,int>> arestas_bipartido;
int kuhn[5*N], used[5*N];
stack <int> marked;
pair <int, int> inverso[2*N];

bool try_kuhn(int v){
    if(used[v]) return false;
    used[v] = 1;
    marked.push(v);
    for(auto x : g[v]){
        if(kuhn[x] == -1){
            kuhn[x] = v;
            return true;
        }
        else if(try_kuhn(kuhn[x])){
            kuhn[x] = v;
            return true;
        }
    }
    return false;
}

int construct_roads(std::vector<int> xx, std::vector<int> yy) {
    srand(time(0));
    int n = xx.size();
    for(int i = 0;i < xx.size();i++){
        x[xx[i]].push_back({yy[i], i});
        y[yy[i]].push_back({xx[i], i});
    }
    // construir grafo de pontos, sem fontes
    for(int i = 2;i < N;i += 2){
        sort(x[i].begin(), x[i].end());
        for(int j = 1;j < x[i].size();j++){
            auto [y1, p1] = x[i][j-1];
            auto [y2, p2] = x[i][j];
            if(y2-y1 == 2){
                arestas.push_back({p1, p2});
                mapear[0][arestas.back()] = arestas.size()-1;
                pontos[mapear[0][arestas.back()]] = {i, y1, i, y2};
                arestas.push_back({p2, p1});
                mapear[0][arestas.back()] = arestas.size()-1;
                pontos[mapear[0][arestas.back()]] = {i, y1, i, y2};
            }
        }
    }
    for(int i = 2;i < N;i += 2){
        sort(y[i].begin(), y[i].end());
        for(int j = 1;j < y[i].size();j++){
            auto [x1, p1] = y[i][j-1];
            auto [x2, p2] = y[i][j];
            if(x2-x1 == 2){
                arestas.push_back({p1, p2});
                mapear[0][arestas.back()] = arestas.size()-1;
                pontos[mapear[0][arestas.back()]] = {x1, i, x2, i};
                arestas.push_back({p2, p1});
                mapear[0][arestas.back()] = arestas.size()-1;
                pontos[mapear[0][arestas.back()]] = {x1, i, x2, i};
            }
        }
    }
    // construir a arvore (acho que sempre da pra montar)
    for(auto [a, b] : arestas){
        g[a].push_back(b);
    }
    dfs(0);
    if(tamanho_componente != n){
        return 0;
    }
    for(int i = 0;i <= n;i++){
        g[i].clear();
    }
    for(auto [a, b] : arvore){
        //cout << a << ' ' << b << '\n';
    }
    // montar grafo bipartido
    vector <int> vertices;
    int qtd_vertices = 0, at = 0;
    for(auto [a, b] : arvore){
        array <int, 4> pt = pontos[mapear[0][{a, b}]];
        if(pt[0] == pt[2]){
            pair <int, int> p1 = {pt[0]-1, pt[1]+1};
            pair <int, int> p2 = {pt[0]+1, pt[1]+1};
            if(mapear[1].find(p1) == mapear[1].end()){
                mapear[1][p1] = qtd_vertices;
                inverso[qtd_vertices] = p1;
                qtd_vertices++;
            }
            if(mapear[1].find(p2) == mapear[1].end()){
                mapear[1][p2] = qtd_vertices;
                inverso[qtd_vertices] = p2;
                qtd_vertices++;
            }
            arestas_bipartido.push_back({at, mapear[1][p1]});
            arestas_bipartido.push_back({at, mapear[1][p2]});
        }
        else{
            pair <int, int> p1 = {pt[0]+1, pt[1]-1};
            pair <int, int> p2 = {pt[0]+1, pt[1]+1};
            if(mapear[1].find(p1) == mapear[1].end()){
                mapear[1][p1] = qtd_vertices;
                inverso[qtd_vertices] = p1;
                qtd_vertices++;
            }
            if(mapear[1].find(p2) == mapear[1].end()){
                mapear[1][p2] = qtd_vertices;
                inverso[qtd_vertices] = p2;
                qtd_vertices++;
            }
            arestas_bipartido.push_back({at, mapear[1][p1]});
            arestas_bipartido.push_back({at, mapear[1][p2]});
        }
        vertices.push_back(at);
        at++;
    }
    int C = arvore.size();
    for(auto [a, b] : arestas_bipartido){
        b += C;
        //cout << a << ' ' << b << '\n';
        g[a].push_back(b);
        g[b].push_back(a);
    }
    sort(vertices.begin(), vertices.end());
    random_shuffle(vertices.begin(), vertices.end());
    memset(kuhn, -1, sizeof kuhn);
    for(auto v : vertices){
        while(!marked.empty()){
            auto x = marked.top();
            marked.pop();
            used[x] = 0;
        }
        try_kuhn(v);
    }
    vector <int> res[4];
    for(int x = 0;x < qtd_vertices;x++){
        int v = kuhn[x+C];
        if(v == -1) continue;
        res[0].push_back(arvore[v].first);
        res[1].push_back(arvore[v].second);
        res[2].push_back(inverso[x].first);
        res[3].push_back(inverso[x].second);
    }
    /*
    u = pontos1
    v = pontos2
    a = x da fonte
    b = y da fonte
    build(u, v, a, b);
    */
    build(res[0], res[1], res[2], res[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