Submission #1166919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166919		PagodePaiva	Fountain Parks (IOI21_parks)	C++20	15 / 100	314 ms	69444 KiB

parks

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

using namespace std;

const int N = 200010;
vector <pair <int, int>> pontos[7];
vector <int> g[N];
map <pair <int, int>, pair <int, int>> bancos;
map <pair <int, int>, int> fontes;
int mark[N];
int cnt;

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

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int n = x.size();
    for(int i = 0;i < x.size();i++){
        pontos[x[i]].push_back({y[i], i});
        fontes[{x[i], y[i]}] = i;
    }
    for(int i = 2;i <= 6;i += 2){
        if(pontos[i].empty()) continue;
        sort(pontos[i].begin(), pontos[i].end());
        for(int j = 1;j < pontos[i].size();j++){
            if(pontos[i][j].first-pontos[i][j-1].first == 2){
                bancos[{(i == 2 ? 1 : i+1), pontos[i][j].first-1}] = {pontos[i][j].second, pontos[i][j-1].second};
            }
        }
    }
    for(int i = 0;i < pontos[4].size();i++){
        auto [y, idx] = pontos[4][i];
        if(fontes.find({2, y}) != fontes.end()){
            bancos[{3, y-1}] = {idx, fontes[{2, y}]};
        }
    }
    for(int i = 0;i < pontos[4].size();i++){
        auto [y, idx] = pontos[4][i];
        if(fontes.find({6, y}) != fontes.end()){
            if(bancos.find({5, y-1}) != bancos.end()){
                if(bancos.find({3, y-1}) != bancos.end()){
                    if(bancos.find({3, y+1}) != bancos.end()){
                        bancos[{3, y+1}] = bancos[{3, y-1}];   
                        bancos[{3, y-1}] = bancos[{5, y-1}];
                        bancos[{5, y-1}] = {idx, fontes[{6, y}]};
                        i++;
                    }
                    else{
                        bancos[{3, y+1}] = bancos[{3, y-1}];    
                        bancos[{3, y-1}] = bancos[{5, y-1}];
                        bancos[{5, y-1}] = {idx, fontes[{6, y}]};
                    }
                }
                else{
                    bancos[{3, y-1}] = bancos[{5, y-1}];
                    bancos[{5, y-1}] = {idx, fontes[{6, y}]};
                }
            }
            else{
                bancos[{5, y-1}] = {idx, fontes[{6, y}]};
            }
        }
    }
    vector <int> u, v, a, b;
    int st = 0;
    for(auto [p, q] : bancos){
        auto [x, y] = p;
        auto [z, w] = q;
        a.push_back(x);
        b.push_back(y);
        u.push_back(z);
        v.push_back(w);
       // cout << x << ' ' << y << ' ' << z << ' ' << w << '\n';
        g[w].push_back(z);
        g[z].push_back(w);
        st = z;
    }
    dfs(st);
    if(cnt != n) return 0;
    build(u, v, a, b);
    return 1;
}

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