Submission #1173076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173076		PagodePaiva	Fountain Parks (IOI21_parks)	C++20	0 / 100	16 ms	33344 KiB

parks

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

using namespace std;

const int N = 200010;
int n;
vector <int> g[5*N];
vector <pair <int, int>> pt;
vector<pair <int, int>> arestas;
vector <pair <int, int>> pontos[N][2];
map <pair <int, int>, int> ruas;
pair <int, int> inv_ruas[5*N];
int to[5*N];
int cor;
int mark[5*N];
int cnt;

void dfs(int v){
    cnt++;
    mark[v] = 1;
    for(auto x : g[v]){
        if(mark[x]) continue;
        dfs(x);
    }
    return;
}

bool kuhn(int v){
    for(auto x : g[v]){
        if(mark[x] == cor) continue;
        mark[x] = cor;
        if(to[x] == -1){
            to[x] = v;
            return true;
        }
        if(kuhn(v)){
            to[x] = v;
            return true;
        }
    }
    return false;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    srand(time(0));
    n = x.size();
    for(int i = 0;i < x.size();i++){
        pontos[x[i]][0].push_back({y[i], i});
        pontos[y[i]][1].push_back({x[i], i});
        pt.push_back({x[i], y[i]});
    }
    for(int i = 2;i <= N;i += 2){
        sort(pontos[i][0].begin(), pontos[i][0].end());
        for(int j = 1;j < pontos[i][0].size();j++){
            if(pontos[i][0][j].first - pontos[i][0][j-1].first == 2){
                arestas.push_back({pontos[i][0][j].second, pontos[i][0][j-1].second});
            }
        }
    }
    for(int i = 2;i <= N;i += 2){
        sort(pontos[i][1].begin(), pontos[i][1].end());
        for(int j = 1;j < pontos[i][1].size();j++){
            if(pontos[i][1][j].first - pontos[i][1][j-1].first == 2){
                arestas.push_back({pontos[i][1][j].second, pontos[i][1][j-1].second});
            }
        }
    }
    int tam1 = arestas.size(), tam2 = 0;
    for(int i = 0;i < arestas.size();i++){
        auto [a, b] = arestas[i];
        auto [p, q] = pt[a];
        auto [r, s] = pt[b];
        if(p == r){
            int a = max(q, s);
            if(ruas.find({p-1, a-1}) == ruas.end()){
                ruas[{p-1,a-1}] = tam1+tam2;
                inv_ruas[ruas[{p-1, a-1}]] = {p-1, a-1};
                tam2++;
            }
            if(ruas.find({p+1, a-1}) == ruas.end()){
                ruas[{p+1,a-1}] = tam1+tam2;
                inv_ruas[ruas[{p+1, a-1}]] = {p+1, a-1};
                tam2++;
            }
            g[i].push_back(ruas[{p-1, a-1}]);
            g[ruas[{p-1, a-1}]].push_back(i);
            g[i].push_back(ruas[{p+1, a-1}]);
            g[ruas[{p+1, a-1}]].push_back(i);
        }   
        else{
            int a = max(p, r);
            if(ruas.find({a-1, q-1}) == ruas.end()){
                ruas[{a-1,q-1}] = tam1+tam2;
                inv_ruas[tam1+tam2] = {a-1, q-1};
                tam2++;
            }
            if(ruas.find({a-1, q+1}) == ruas.end()){
                ruas[{a-1,q+1}] = tam1+tam2;
                inv_ruas[tam1+tam2] = {a-1, q+1};
                tam2++;
            }
            g[i].push_back(ruas[{a-1, q-1}]);
            g[ruas[{a-1, q-1}]].push_back(i);
            g[i].push_back(ruas[{a-1, q+1}]);
            g[ruas[{a-1, q+1}]].push_back(i);    
        }
    }
    vector <int> vertices, complemento;
    for(int i = (tam1 < tam2 ? 0 : tam1);i < (tam1 < tam2 ? tam1 : tam1+tam2);i++){
        vertices.push_back(i);
    }    
    for(int i = (tam1 >= tam2 ? 0 : tam1);i < (tam1 >= tam2 ? tam1 : tam1+tam2);i++){
        complemento.push_back(i);
    }    
    random_shuffle(vertices.begin(), vertices.end());
    memset(to, -1, sizeof to);
    for(auto v : vertices){
        cor++;
        kuhn(v);
    }
    vector <pair <int, int>> matching;
    for(auto x : complemento){
        if(to[x] == -1) continue;
        matching.push_back({min(to[x], x), max(to[x], x)});
    }
    vector <int> ans[4];
    for(int i = 0;i < 5*N;i++)
        g[i].clear();
    for(auto [a, b] : matching){
        pair <int, int> reta = arestas[a];
        pair <int, int> q = inv_ruas[b];
        ans[0].push_back(reta.first);
        ans[1].push_back(reta.second);
        ans[2].push_back(q.first);
        ans[3].push_back(q.second);
        g[reta.first].push_back(reta.second);
        g[reta.second].push_back(reta.first);
    }
    memset(mark, 0, sizeof mark);
    dfs(0);
    if(cnt != n) return 0;
    build(ans[0], ans[1], ans[2], ans[3]);
    return 1;   
}

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