Submission #1209314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209314		bangan	Fountain Parks (IOI21_parks)	C++20	30 / 100	134 ms	51356 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>

constexpr int X = 6;
constexpr int Y = 2E5;

int pos[X + 1][Y + 1];

int construct_roads(std::vector<int> x_in, std::vector<int> y_in) {
    int n = x_in.size();

    {
        int max = *std::max_element(x_in.begin(), x_in.end());
        assert(max <= X);
    }

    for (int i = 0; i < n; i++) {
        pos[x_in[i]][y_in[i]] = i + 1;
    }

    std::vector<int> v, u;
    std::vector<int> a, b;

    for (int y = 2; y + 2 <= Y; y += 2) {
        if (pos[2][y] != 0 && pos[2][y + 2] != 0) {
            v.push_back(pos[2][y]);
            u.push_back(pos[2][y + 2]);
            a.push_back(1);
            b.push_back(y + 1);
        }
    }

    for (int y = 2; y + 2 <= Y; y += 2) {
        if (pos[4][y] != 0 && pos[4][y + 2] != 0) {
            v.push_back(pos[4][y]);
            u.push_back(pos[4][y + 2]);
            a.push_back(y % 4 == 0 ? 5 : 3);
            b.push_back(y + 1);
            pos[a.back()][y + 1] = -1;
        }
    }

    for (int y = 2; y + 2 <= Y; y += 2) {
        if (pos[6][y] != 0 && pos[6][y + 2] != 0) {
            v.push_back(pos[6][y]);
            u.push_back(pos[6][y + 2]);
            a.push_back(7);
            b.push_back(y + 1);
        }
    }

    for (int y = 2; y <= Y; y += 2) {
        if (pos[2][y] != 0 && pos[4][y] != 0) {
            if (pos[3][y - 1] != -1) {
                v.push_back(pos[2][y]);
                u.push_back(pos[4][y]);
                a.push_back(3);
                b.push_back(y - 1);
                pos[3][y - 1] = -1;
            } 
            else if (pos[3][y + 1] != -1) {
                v.push_back(pos[2][y]);
                u.push_back(pos[4][y]);
                a.push_back(3);
                b.push_back(y + 1);
                pos[3][y + 1] = -1;
            }
        }
        if (pos[4][y] != 0 && pos[6][y] != 0) {
            if (pos[5][y - 1] != -1) {
                v.push_back(pos[4][y]);
                u.push_back(pos[6][y]);
                a.push_back(5);
                b.push_back(y - 1);
                pos[5][y - 1] = -1;
            }
            else if (pos[5][y + 1] != -1) {
                v.push_back(pos[4][y]);
                u.push_back(pos[6][y]);
                a.push_back(5);
                b.push_back(y + 1);
                pos[5][y + 1] = -1;
            }
        }
    }

    std::vector<std::vector<int>> adj(n + 1);
    for (int i = 0; i < v.size(); i++) {
        adj[v[i]].push_back(i);
        adj[u[i]].push_back(i);
    }

    std::vector<bool> vis(n + 1);
    auto dfs = [&](auto self, int x) -> void {
        vis[x] = true;
        for (int i : adj[x]) {
            int y = v[i] ^ u[i] ^ x;
            if (!vis[y]) {
                self(self, y);
            }
        }
    };
    dfs(dfs, 1);

    if (std::count(vis.begin(), vis.end(), true) == n) {
        for (int &x : v) x--;
        for (int &y : u) y--;
        build(v, u, a, b);
        return 1;
    }

    return 0;
}

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