Submission #1233535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233535		rythm_of_knight	Fountain Parks (IOI21_parks)	C++17	30 / 100	272 ms	44588 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()

using namespace std;

const int N = 2e5 + 5;
int f[N], sz[N];
vector <ar <int, 2>> g[N];

int father(int x) {
    if (f[x] != f[f[x]])
        return f[x] = father(f[x]);
    return f[x];
}

int dsu(int a, int b) {
    a = father(a), b = father(b);
    if (a == b)
        return 0;
    if (sz[a] < sz[b])
        swap(a, b);
    sz[a] += sz[b];
    f[b] = a;
    return 1;
}

int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    map <ar <int, 2>, int> mp;
    int mn = 1e9, mx = 0;
    for (int i = 0; i < n; i++)
        sz[i] = 1, f[i] = i;
    for (int i = 0; i < n; i++)
        mn = min(mn, x[i]), mx = max(mx, x[i]), g[x[i]].push_back({y[i], i}), mp[{x[i], y[i]}] = i;
    vector <int> u, v, bx, by;
    set <ar <int, 2>> tkn;
    for (int i = mn; i <= mx; i += 2) {
        sort(all(g[i]));
        if (i == mn) {
            for (int j = 1; j < g[i].size(); j++) {
                int na = g[i][j - 1][1], nb = g[i][j][1];
                if (y[nb] - y[na] == 2) {
                    int tmp = dsu(na, nb);
                    u.push_back(na);
                    v.push_back(nb);
                    bx.push_back(i - 1);
                    by.push_back(y[nb] - 1);
                }
            }
        } else if (i == mx) {
            for (int j = 1; j < g[i].size(); j++) {
                int na = g[i][j - 1][1], nb = g[i][j][1];
                if (y[nb] - y[na] == 2) {
                    int tmp = dsu(na, nb);
                    u.push_back(na);
                    v.push_back(nb);
                    bx.push_back(i + 1);
                    by.push_back(y[nb] - 1);
                }
            }
            for (int j = 0; j < g[i].size(); j++) {
                ar <int, 2> dream = {i - 2, g[i][j][0]};
                if (mp.count(dream)) {
                    int k = mp[dream], nb = g[i][j][1];
                    if (dsu(k, nb)) {
                        u.push_back(k);
                        v.push_back(nb);
                        bx.push_back(i - 1);
                        if (tkn.count({i - 1, y[nb] - 1})) {
                            by.push_back(y[nb] + 1);
                            tkn.insert({i - 1, y[nb] + 1});
                        } else {
                            by.push_back(y[nb] - 1);
                            tkn.insert({i - 1, y[nb] - 1});
                        }
                    }
                }
            }
        } else {
            for (int j = 1; j < g[i].size(); j++) {
                if (g[i][j][0] - g[i][j - 1][0] == 2) {
                    int tmp = dsu(g[i][j - 1][1], g[i][j][1]);
                }
            }
            for (int j = 0; j < g[i].size(); j++) {
                ar <int, 2> dream = {i - 2, g[i][j][0]};
                if (mp.count(dream)) {
                    int k = mp[dream], nb = g[i][j][1];
                    if (dsu(k, g[i][j][1])) {
                        u.push_back(k);
                        v.push_back(nb);
                        bx.push_back(i - 1);
                        by.push_back(y[nb] - 1);
                        tkn.insert({i - 1, y[nb] - 1});
                    }
                }
            }
            for (int j = 1; j < g[i].size(); j++) {
                int na = g[i][j - 1][1], nb = g[i][j][1];
                if (y[nb] - y[na] == 2) {
                    u.push_back(na);
                    v.push_back(nb);
                    by.push_back(y[nb] - 1);
                    if (tkn.count({i - 1, y[nb] - 1})) {
                        bx.push_back(i + 1);
                        tkn.insert({i + 1, y[nb] - 1});
                    } else {
                        bx.push_back(i - 1);
                        tkn.insert({i - 1, y[nb] - 1});
                    }
                }
            }
        }
    }
    // for (int i = 0; i < n; i++)
    //     f[i] = i, sz[i] = 1;
    // int m = u.size();
    // for (int i = 0; i < m; i++)
    //     int tmp = dsu(u[i], v[i]);
    int fa = father(n - 1);
    for (int i = 0; i < n; i++)
        if (father(i) != fa)
            return 0;
    build(u, v, bx, by);
    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