Submission #529329

#	Time	Username	Problem	Language	Result	Execution time	Memory
529329		SHZhang	Fountain Parks (IOI21_parks)	C++17	100 / 100	997 ms	65396 KiB

parks

#include "parks.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <utility>

using namespace std;

int n;
int uf[200005];

map<pair<int, int>, int> pt2idx;

int fin(int x)
{
    if (uf[x] == x) return x;
    return uf[x] = fin(uf[x]);
}

void un(int x, int y)
{
    x = fin(x);
    y = fin(y);
    if (x != y) uf[x] = y;
}

vector<int> ansu, ansv, ansa, ansb;

bool build_edge(int x1, int y1, int x2, int y2, int bx, int by)
{
    int p1 = pt2idx[make_pair(x1, y1)];
    int p2 = pt2idx[make_pair(x2, y2)];
    if (fin(p1) == fin(p2)) return false;
    un(p1, p2);
    ansu.push_back(p1);
    ansv.push_back(p2);
    ansa.push_back(bx);
    ansb.push_back(by);
    return true;
}

int construct_roads(vector<int> x, vector<int> y) {
    n = x.size();
    for (int i = 0; i < n; i++) uf[i] = i;
    set<pair<int, int> > st, bench;
    for (int i = 0; i < n; i++) {
        st.insert(make_pair(x[i], y[i]));
        pt2idx[make_pair(x[i], y[i])] = i;
        bench.insert(make_pair(x[i]-1, y[i]-1));
        bench.insert(make_pair(x[i]-1, y[i]+1));
        bench.insert(make_pair(x[i]+1, y[i]-1));
        bench.insert(make_pair(x[i]+1, y[i]+1));
    }
    while (!bench.empty()) {
        pair<int, int> cur = *(bench.begin());
        bench.erase(bench.begin());
        if ((cur.first + cur.second) % 4 == 0) {
            if (st.count(make_pair(cur.first - 1, cur.second - 1)) &&
                st.count(make_pair(cur.first + 1, cur.second - 1))) {
                if (build_edge(cur.first - 1, cur.second - 1,
                    cur.first + 1, cur.second - 1, cur.first, cur.second)) continue;
            }
            if (st.count(make_pair(cur.first - 1, cur.second + 1)) &&
                st.count(make_pair(cur.first + 1, cur.second + 1))) {
                build_edge(cur.first - 1, cur.second + 1,
                    cur.first + 1, cur.second + 1, cur.first, cur.second);
            }
        } else {
            if (st.count(make_pair(cur.first - 1, cur.second - 1)) &&
                st.count(make_pair(cur.first - 1, cur.second + 1))) {
                if (build_edge(cur.first - 1, cur.second - 1,
                    cur.first - 1, cur.second + 1, cur.first, cur.second)) continue;
            }
            if (st.count(make_pair(cur.first + 1, cur.second - 1)) &&
                st.count(make_pair(cur.first + 1, cur.second + 1))) {
                build_edge(cur.first + 1, cur.second - 1,
                    cur.first + 1, cur.second + 1, cur.first, cur.second);
            }
        }
    }
    if (ansa.size() < n - 1) {
        return 0;
    }
    build(ansu, ansv, ansa, ansb);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:83:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |     if (ansa.size() < n - 1) {
      |         ~~~~~~~~~~~~^~~~~~~

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