Submission #814328

#	Time	Username	Problem	Language	Result	Execution time	Memory
814328		PixelCat	Fountain Parks (IOI21_parks)	C++17	15 / 100	270 ms	26424 KiB

parks

#include "parks.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200'000;

struct DSU {
    int p[MAXN + 10];
    void init() {
        memset(p, -1, sizeof(p));
    }
    int find(int n) {
        if(p[n] < 0) return n;
        return p[n] = find(p[n]);
    }
    bool uni(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return false;
        p[b] = a;
        return true;
    }
} dsu;

struct PT {
    int id, x, y;
};

int construct_roads(std::vector<int> X, std::vector<int> Y) {
    if (sz(X) == 1) {
        build({}, {}, {}, {});
        return 1;
    }
    int n = sz(X);

    map<pii, int> mp;
    For(i, 0, n - 1) {
        mp[pii(X[i], Y[i])] = i;
    }
    auto find = [&](int x, int y) {
        if(mp.count(pii(x, y))) return mp[pii(x, y)];
        return -1;
    };
    vector<int> U, V, A, B;
    dsu.init();
    int cnt = 0;
    
    for(int i = 2; i < MAXN; i += 2) {
        int p1 = find(2, i);
        int p2 = find(2, i + 2);
        if(p1 >= 0 && p2 >= 0 && dsu.uni(p1, p2)) {
            U.eb(p1);
            V.eb(p2);
            A.eb(1);
            B.eb(i + 1);
            cnt++;
        }
    }
    for(int i = 2; i < MAXN; i += 2) {
        int p1 = find(4, i);
        int p2 = find(4, i + 2);
        if(p1 >= 0 && p2 >= 0 && dsu.uni(p1, p2)) {
            U.eb(p1);
            V.eb(p2);
            A.eb(5);
            B.eb(i + 1);
            cnt++;
        }
    }
    for(int i = 2; i <= MAXN; i += 2) {
        int p1 = find(2, i);
        int p2 = find(4, i);
        if(p1 >= 0 && p2 >= 0 && dsu.uni(p1, p2)) {
            U.eb(p1);
            V.eb(p2);
            A.eb(3);
            B.eb(i + 1);
            cnt++;
        }
    }
    if(cnt < n - 1) return 0;

    build(U, V, A, B);
    return 1;
}

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