Submission #685024

#	Time	Username	Problem	Language	Result	Execution time	Memory
685024		sharaelong	Fountain Parks (IOI21_parks)	C++17	15 / 100	429 ms	71056 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

struct DisjointSet {
    int n;
    vector<int> parent, rank;
    DisjointSet(int _n) : n(_n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        rank.resize(n, 0);
    }

    int find(int u) {
        return parent[u] = (u == parent[u] ? u : find(parent[u]));
    }

    void merge(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return;
        if (rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if (rank[u] == rank[v]) ++rank[v];
    }
};

int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int a, int b) {
        return pii{x[a],y[a]} < pii{x[b], y[b]};
    });
    
    DisjointSet dsu(n);
    map<pii, int> fountains;
    vector<vector<pii>> points(200001);
    int min_x = 200000;
    set<pii> benches;
    vector<int> u, v, a, b;
    for (int i=0; i<n; ++i) fountains[{ x[i], y[i] }] = i, min_x = min(min_x, x[i]);
    for (int i=0; i<n; ++i) points[x[i]].push_back({ y[i], i });
    for (int i=0; i<points.size(); i+=2) sort(points[i].begin(), points[i].end());
    for (int j=0; j+1<points[min_x].size(); ++j) {
        if (points[min_x][j].first + 2 == points[min_x][j+1].first) {
            dsu.merge(points[min_x][j].second, points[min_x][j+1].second);
            u.push_back(points[min_x][j].second);
            v.push_back(points[min_x][j+1].second);
            a.push_back(min_x-1);
            b.push_back(points[min_x][j].first + 1);
            benches.insert({ points[min_x][j].first + 1, min_x-1 });
        }
    }

    for (int x=min_x+2; x<points.size(); x+=2) {
        for (int j=0; j<points[x].size(); ++j) {
            auto[y1, i1] = points[x][j];
            if (fountains.find({ x-2, y1 }) != fountains.end()) {
                int idx = fountains[{x-2, y1}];
                if (dsu.find(idx) != dsu.find(i1)) {
                    dsu.merge(idx, i1);
                    u.push_back(idx);
                    v.push_back(i1);
                    a.push_back(x-1);
                    if (benches.find({x-1, y1-1}) != benches.end()) {
                        assert(benches.find({x-1, y1+1}) == benches.end());
                        b.push_back(y1+1);
                    } else {
                        b.push_back(y1-1);
                    }
                    benches.insert({ a.back(), b.back() });
                }
            }
            if (j+1 == points[x].size()) break;
            
            auto[y2, i2] = points[x][j+1];
            if (y1 + 2 == y2) {
                dsu.merge(i1, i2);
                u.push_back(i1);
                v.push_back(i2);
                b.push_back(y1+1);
                if (benches.find({x-1, y1+1}) != benches.end()) {
                    assert(benches.find({x+1, y1+1}) == benches.end());
                    a.push_back(x+1);
                } else {
                    a.push_back(x-1);
                }
                benches.insert({ a.back(), b.back() });
            }
        }
    }

    for (int i=1; i<n; ++i) {
        if (dsu.find(i) != dsu.find(0)) {
            return 0;
        }
    }
    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:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i=0; i<points.size(); i+=2) sort(points[i].begin(), points[i].end());
      |                   ~^~~~~~~~~~~~~~
parks.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int j=0; j+1<points[min_x].size(); ++j) {
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~
parks.cpp:57:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int x=min_x+2; x<points.size(); x+=2) {
      |                         ~^~~~~~~~~~~~~~
parks.cpp:58:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int j=0; j<points[x].size(); ++j) {
      |                       ~^~~~~~~~~~~~~~~~~
parks.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             if (j+1 == points[x].size()) break;
      |                 ~~~~^~~~~~~~~~~~~~~~~~~

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