Submission #1026321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026321		HappyCapybara	Fountain Parks (IOI21_parks)	C++17	15 / 100	217 ms	49940 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
using namespace std;

vector<int> p;

int find(int a){
    if (p[a] == a) return a;
    else return p[a] = find(p[a]);
}

void merge(int a, int b){
    a = find(a);
    b = find(b);
    if (a == b) return;
    p[a] = b;
}

int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    unordered_map<int,vector<pair<int,int>>> r, c;
    for (int i=0; i<n; i++){
        r[y[i]].push_back({x[i], i});
        c[x[i]].push_back({y[i], i});
    }
    vector<pair<int,int>> el;
    //cout << "a\n";
    for (int i=2; i<=200000; i++){
        if (c[i].size() > 1){
            sort(c[i].begin(), c[i].end());
            for (int j=0; j<c[i].size()-1; j++){
                if (c[i][j+1].first-c[i][j].first == 2) el.push_back({c[i][j].second, c[i][j+1].second});
            }
        }
        if (r[i].size() > 1){
            sort(r[i].begin(), r[i].end());
            for (int j=0; j<r[i].size()-1; j++){
                if (r[i][j+1].first-r[i][j].first == 2) el.push_back({r[i][j].second, r[i][j+1].second});
            }
        }
    }
    p.resize(n);
    for (int i=0; i<n; i++) p[i] = i;
    //cout << "b\n";
    vector<int> u, v, a, b;
    int done = 0;
    int cur = -1;
    while (done < n-1){
        cur++;
        //cout << cur << " " << done << "\n";
        if (cur == el.size()) return 0;
        if (find(el[cur].first) == find(el[cur].second)) continue;
        //cout << "a\n";
        merge(el[cur].first, el[cur].second);
        done++;
        u.push_back(el[cur].first);
        v.push_back(el[cur].second);
        //cout << "b\n";
        if (x[el[cur].first] == x[el[cur].second]){
            b.push_back((y[el[cur].first]+y[el[cur].second])/2);
            if (x[el[cur].first] == 2) a.push_back(1);
            else a.push_back(x[el[cur].first]+1);
        }
        else {
            a.push_back((x[el[cur].first]+x[el[cur].second])/2);
            b.push_back(y[el[cur].first]-1);
        }
        //cout << "c\n";
    }
    //cout << "c\n";
    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:31:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             for (int j=0; j<c[i].size()-1; j++){
      |                           ~^~~~~~~~~~~~~~
parks.cpp:37:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for (int j=0; j<r[i].size()-1; j++){
      |                           ~^~~~~~~~~~~~~~
parks.cpp:51:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         if (cur == el.size()) return 0;
      |             ~~~~^~~~~~~~~~~~

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