Submission #1166945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166945		PagodePaiva	Fountain Parks (IOI21_parks)	C++20	5 / 100	198 ms	58176 KiB

parks

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

using namespace std;

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

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) {
    n = x.size();
    for(int i = 0;i < n;i++){
        pontos[x[i]].push_back({y[i], i});
        pontos2[y[i]].push_back({x[i], i});
    }
    for(int i = 2;i < N;i++){
        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){
                if((pontos[i][j-1].first/2)%2 == 1){
                    fontes[{i-1, pontos[i][j-1].first+1}] = make_pair(pontos[i][j].second, pontos[i][j-1].second);
                }
                else{
                    fontes[{i+1, pontos[i][j-1].first+1}] = make_pair(pontos[i][j].second, pontos[i][j-1].second);                    
                }
            }
        }
    }
    for(int i = 2;i < N;i++){
        if(pontos2[i].empty()) continue;
        sort(pontos2[i].begin(), pontos2[i].end());
        for(int j = 1;j < pontos2[i].size();j++){
            if(pontos2[i][j].first - pontos2[i][j-1].first == 2){
                if(fontes.find({pontos2[i][j].first-1, i-1}) != fontes.end()){
                    fontes[{pontos2[i][j].first-1, i+1}] = make_pair(pontos2[i][j].second, pontos2[i][j-1].second);
                }
                else{
                    fontes[{pontos2[i][j].first-1, i-1}] = make_pair(pontos2[i][j].second, pontos2[i][j-1].second);                    
                }
            }
        }
    }
    vector <int> u, v, a, b;
    int st = 0;
    for(auto [p, q] : fontes){
        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;
    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