Submission #582500

#	Time	Username	Problem	Language	Result	Execution time	Memory
582500		georgievskiy	Fountain Parks (IOI21_parks)	C++17	5 / 100	450 ms	78896 KiB

parks

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

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

void dfs(int v, int c) {
    if (used[v])
        return;
    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}};
    bool p0 = field.count(t[0]) && !used[field[t[0]]];
    bool p1 = field.count(t[1]) && !used[field[t[1]]];
    bool p2 = field.count(t[2]) && !used[field[t[2]]];
    bool p3 = field.count(t[3]) && !used[field[t[3]]];
    if (p0 && p1) {
        int x = field[t[0]], y =field[t[1]];
        type[e.size()] = 0; e.push_back({v, x});
        dfs(x, 1);
        type[e.size()] = 1; e.push_back({v, y});
        dfs(y, 0);
    } else if (p0) {
        int x = field[t[0]];
        type[e.size()] = c; e.push_back({v, x});
        dfs(x, !c);
    } else if (p1) {
        int y = field[t[1]];
        type[e.size()] = c; e.push_back({v, y});
        dfs(y, !c);
    }
    if (p2) {
        int u = field[t[2]];
        e.push_back({v, u});
        dfs(u, c);
    }
    if (p3) {
        int u = field[t[3]];
        e.push_back({v, u});
        dfs(u, c);
    }
}

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, 0);
    if (count(used.begin(), used.end(), 0))
        return 0;

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

    for (int i = 0; i < e.size(); i++) {
        if (type.count(i)) {
            pii p = e[i];
            pii v = {x[p.first], y[p.first]}, u = {x[p.second], y[p.second]};
            if (type[i])
                a[i] = (v.first + u.first) / 2, b[i] = v.first - 1;
            else
                a[i] = (v.first + u.first) / 2, b[i] = v.first + 1;
            field[{a[i], b[i]}] = -1;
        }
    }

    for (int i = 0; i < e.size(); i++) {
        if (!type.count(i)) {
            pii p = e[i];
            pii v = {x[p.first], y[p.first]}, u = {x[p.second], y[p.second]};

            a[i] = v.first - 1, b[i] = (v.second + u.second) / 2;
            if (field.count({a[i], b[i]}))
                a[i] += 2;

            if (field.count({a[i], b[i]}))
                return 0;
        }
    }

    vector<int> us, vs;
    for (auto p : e)
        us.push_back(p.first), vs.push_back(p.second);

    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:61: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]
   61 |     for (int i = 0; i < e.size(); i++) {
      |                     ~~^~~~~~~~~~
parks.cpp:73: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]
   73 |     for (int i = 0; i < e.size(); i++) {
      |                     ~~^~~~~~~~~~

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