Submission #1240787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240787		trimkus	Fountain Parks (IOI21_parks)	C++20	30 / 100	328 ms	51352 KiB

parks

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

using namespace std;

struct DSU {
    vector<int> e;
    DSU (int n) {
        e = vector<int>(n, -1);
    }
    int get(int x) {
        return e[x] < 0 ? x : e[x] = get(e[x]);
    }
    int size(int x) {
        return -e[get(x)];
    }
    bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) swap(x, y);
        e[x] += e[y];
        e[y] = x;
        return true;
    }
};

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int N = x.size();
    vector<map<int, int>> mp(N + 10);
    for (int i = 0; i < N; ++i) {
        mp[x[i]][y[i]] = i;
    }
    vector<map<int, int>> vis(N + 10);
    DSU dsu(N);
    vector<int> u, v, a, b;
    for (int i = 0; i < N; ++i) {
        if (mp[x[i]].count(y[i] + 2)) {
            int j = mp[x[i]][y[i] + 2];
            // cout << "x match:\n";
            // cout << x[i] << " " << y[i] << "\n";
            // cout << x[j] << " " << y[j] << "\n\n";
            dsu.unite(i, j);
            u.push_back(i);
            v.push_back(j);
            int ny = y[i] + 1;
            int nx;
            if (x[i] == 2) {
                nx = 1;
            } else if (x[i] == 6) {
                nx = 7;
            } else {
                if ((y[i] / 2) % 2) {
                    nx = 5;
                } else {
                    nx = 3;
                }
            }
            a.push_back(nx);
            b.push_back(ny);
            vis[nx][ny] = 1;
        }
    }
    for (int i = 0; i < N; ++i) {
        if (mp[x[i] + 2].count(y[i])) {
            int j = mp[x[i] + 2][y[i]];
            if (dsu.unite(i, j)) {
            //     cout << x[i] << " " << y[i] << "\n";
            // cout << x[j] << " " << y[j] << "\n\n";
                u.push_back(i);
                v.push_back(j);
                int nx = x[i] + 1;
                int ny = y[i] - 1;
                if (vis[nx].count(ny)) ny = y[i] + 1;
                assert(!vis[nx].count(ny));
                a.push_back(nx);
                b.push_back(ny);
                vis[nx][ny] = 1;
            }
        }
    }
    // cout << dsu.size(0) << "\n";
    if (dsu.size(0) != N) return 0;
    build(u, v, a, b);
    return 1;
}

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