Submission #1026323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026323		HappyCapybara	Fountain Parks (IOI21_parks)	C++17	15 / 100	167 ms	56600 KiB

parks

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

#define ll long long

vector<int> p;

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

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

int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    int mx = 0;
    unordered_map<int,vector<pair<int,int>>> r, c;
    for (int i=0; i<n; i++){
        mx = max(mx, x[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;
    unordered_set<int> benches;
    while (done < n-1){
        cur++;
        //cout << cur << " " << done << "\n";
        if (cur == el.size()) return 0;
        if (findp(el[cur].first) == findp(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 if (x[el[cur].first] == mx) a.push_back(x[el[cur].first]+1);
            else {
                if (min(y[el[cur].first], y[el[cur].second]) % 4) a.push_back(x[el[cur].first]-1);
                else a.push_back(x[el[cur].first]+1);
            }
        }
        else {
            a.push_back((x[el[cur].first]+x[el[cur].second])/2);
            if (mx == 4) b.push_back(y[el[cur].first]-1);
            else {
                int q = y[el[cur].first]+1, r = y[el[cur].first]-1;
                if (benches.find(a.back()*100000+q) != benches.end() && benches.find(a.back()*100000+r) != benches.end()) return 0;
                if (benches.find(a.back()*100000+q) != benches.end()) b.push_back(r);
                else if (benches.find(a.back()*100000+r) != benches.end()) b.push_back(q);
                else if (min(x[el[cur].first], x[el[cur].second]) % 4) b.push_back(q);
                else b.push_back(r);
            }
        }
        benches.insert(a.back()*100000+b.back());
        //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:35: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]
   35 |             for (int j=0; j<c[i].size()-1; j++){
      |                           ~^~~~~~~~~~~~~~
parks.cpp:41: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]
   41 |             for (int j=0; j<r[i].size()-1; j++){
      |                           ~^~~~~~~~~~~~~~
parks.cpp:56: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]
   56 |         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