oj.uz

Submission #814326

# Submission time Handle Problem Language Result Execution time Memory
814326 2023-08-08T06:51:48 Z PixelCat Fountain Parks (IOI21_parks) C++17
0 / 100
 2 ms 980 KB 
#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();
    
    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);
        }
    }
    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);
        }
    }
    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);
        }
    }

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Incorrect 2 ms 980 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Incorrect 2 ms 980 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Incorrect 2 ms 980 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Incorrect 2 ms 980 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Incorrect 2 ms 980 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Incorrect 2 ms 980 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -