Submission #583092

#	Time	Username	Problem	Language	Result	Execution time	Memory
583092		georgievskiy	Fountain Parks (IOI21_parks)	C++17	55 / 100	773 ms	91772 KiB

parks

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

int n;
map<pii, int> field;
vector<int> x, y, used;
vector<pii> e;

void dfs(int v, int p) {
    if (used[v])
        return;
    if (p != -1)
        e.emplace_back(v, p);
    used[v] = 1;
    int vx = x[v], vy = y[v];
    pii t[4] = {{vx + 2, vy}, {vx - 2, vy}, {vx, vy + 2}, {vx, vy - 2}};
    for (int i = 0; i < 4; i++)
        if (field.count(t[i]))
            dfs(field[t[i]], v);
}

int construct_roads(std::vector<int> X, std::vector<int> Y) {
    n = X.size(), x = X, y = Y;
    for (int i = 0; i < n; i++)
        field[{x[i], y[i]}] = i;

    used.resize(n, 0);
    dfs(0, -1);
    if (count(used.begin(), used.end(), 0))
        return 0;

    vector<int> us, vs;
    set<pii> loc;

    for (int i = 0; i < e.size(); i++) {
        us.push_back(e[i].first), vs.push_back(e[i].second);
        pii p = e[i];
        pii mid = {(x[p.first] + x[p.second]) / 2, (y[p.first] + y[p.second]) / 2};
        field[mid] = i;
        if (x[p.first] == x[p.second]) {
            loc.insert({mid.first-1, mid.second});
            loc.insert({mid.first+1, mid.second});
        } else {
            loc.insert({mid.first, mid.second+1});
            loc.insert({mid.first, mid.second-1});
        }
    }

    vector<int> a(e.size(), -1), b(e.size());

    if (*max_element(x.begin(), x.end()) <= 4) {

        for (pii p : loc) {
            if (p.first == 1) {
                pii p1 = p;
                p1.first++;
                if (field.count(p1)) {
                    a[field[p1]] = p.first, b[field[p1]] = p.second;
                    field.erase(p1);
                }
            } else if (p.first == 5) {
                pii p1 = p;
                p1.first--;
                if (field.count(p1)) {
                    a[field[p1]] = p.first, b[field[p1]] = p.second;
                    field.erase(p1);
                }
            } else {
                pii p1 = p, p2 = p;
                p1.second++, p2.second--;
                if (field.count(p1)) {
                    a[field[p1]] = p.first, b[field[p1]] = p.second;
                    field.erase(p1);
                } else if (field.count(p2)) {
                    a[field[p2]] = p.first, b[field[p2]] = p.second;
                    field.erase(p2);
                }
            }
        }

    } else
    for (pii p : loc) {
        pii p1 = p, p2 = p;
        if ((p.first / 2 + p.second / 2) % 2)
            p1.first++, p2.first--;
        else
            p1.second++, p2.second--;

        if (field.count(p1)) {
            a[field[p1]] = p.first, b[field[p1]] = p.second;
            field.erase(p1);
        } else if (field.count(p2)) {
            a[field[p2]] = p.first, b[field[p2]] = p.second;
            field.erase(p2);
        }
    }

    if (count(a.begin(), a.end(), -1))
        return 0;

    build(us, vs, a, b);

    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:37:23: 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 i = 0; i < e.size(); i++) {
      |                     ~~^~~~~~~~~~

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