oj.uz

Submission #1021416

# Submission time Handle Problem Language Result Execution time Memory
1021416 2024-07-12T17:47:16 Z Wael Fountain Parks (IOI21_parks) C++17
5 / 100
 262 ms 56232 KB 
#include "parks.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;

struct DSU {
    int n, cnt;
    vector<int> f, sz;
    DSU(int n) : n(n), cnt(n) {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
        sz.resize(n, 1);
    }

    int find(int u) {
        if (f[u] == u) return u;
        return f[u] = find(f[u]);
    }

    void merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        --cnt;
        if (sz[v] > sz[u]) {
            swap(u, v);
        }
        f[v] = u;
        sz[u] += sz[v];
    }

    bool same(int u, int v) {
        return find(u) == find(v);
    }
};

int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();

    int N = 2e5;
    vector<map<int, int>> id(N + 1);

    for (int i = 0; i < n; ++i) {
        id[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 (id[x[i]].count(y[i] + 2)) {
            int j = id[x[i]][y[i] + 2];
            dsu.merge(i, j);
            u.push_back(i);
            v.push_back(j);
            if (x[i] == 6) {
                a.push_back(x[i] + 1);
                b.push_back(y[i] + 1);
                vis[x[i] + 1][y[i] + 1] = 1;
            } else if (x[i] == 2) {
                a.push_back(x[i] - 1);
                b.push_back(y[i] + 1);
                vis[x[i] - 1][y[i] + 1] = 1;
            } else {
                if ((y[i] / 2) % 2) {
                    a.push_back(x[i] + 1);
                    b.push_back(y[i] + 1);
                    vis[x[i] + 1][y[i] + 1] = 1;
                } else {
                    a.push_back(x[i] - 1);
                    b.push_back(y[i] + 1);
                    vis[x[i] - 1][y[i] + 1] = 1;
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (id[x[i] + 2].count(y[i])) {
            int j = id[x[i] + 2][y[i]];
            if (dsu.same(i, j) == 0) {
                u.push_back(i);
                v.push_back(j);
                dsu.merge(i, j);
                if (vis[x[i] + 1][y[i] - 1] == 0) {
                    a.push_back(x[i] + 1);
                    b.push_back(y[i] - 1);
                    vis[x[i] + 1][y[i] - 1] = 1;
                } else {
                    a.push_back(x[i] + 1);
                    b.push_back(y[i] + 1);
                    vis[x[i] + 1][y[i] + 1] = 1;
                }
            }
        }

        if (id[x[i] - 2].count(y[i])) {
            int j = id[x[i] - 2][y[i]];
            if (dsu.same(i, j) == 0) {
                u.push_back(i);
                v.push_back(j);
                dsu.merge(i, j);
                if (vis[x[i] - 1][y[i] - 1]) {
                    a.push_back(x[i] - 1);
                    b.push_back(y[i] - 1);
                    vis[x[i] - 1][y[i] - 1] = 1;
                } else {
                    a.push_back(x[i] - 1);
                    b.push_back(y[i] + 1);
                    vis[x[i] - 1][y[i] + 1] = 1;
                }
            }
        }
    }

    if (dsu.cnt == 1) {
        build(u, v, a, b);
        return 1;
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 9 ms 19192 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 9 ms 19124 KB Output is correct
7 Correct 8 ms 19168 KB Output is correct
8 Correct 8 ms 19036 KB Output is correct
9 Correct 138 ms 36280 KB Output is correct
10 Correct 14 ms 20992 KB Output is correct
11 Correct 46 ms 28356 KB Output is correct
12 Correct 20 ms 21692 KB Output is correct
13 Correct 31 ms 25296 KB Output is correct
14 Correct 9 ms 19292 KB Output is correct
15 Correct 9 ms 19288 KB Output is correct
16 Correct 135 ms 36276 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 9 ms 19192 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 9 ms 19124 KB Output is correct
7 Correct 8 ms 19168 KB Output is correct
8 Correct 8 ms 19036 KB Output is correct
9 Correct 138 ms 36280 KB Output is correct
10 Correct 14 ms 20992 KB Output is correct
11 Correct 46 ms 28356 KB Output is correct
12 Correct 20 ms 21692 KB Output is correct
13 Correct 31 ms 25296 KB Output is correct
14 Correct 9 ms 19292 KB Output is correct
15 Correct 9 ms 19288 KB Output is correct
16 Correct 135 ms 36276 KB Output is correct
17 Correct 9 ms 19036 KB Output is correct
18 Incorrect 8 ms 19220 KB Tree @(3, 5) appears more than once: for edges on positions 0 and 2
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 9 ms 19192 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 9 ms 19124 KB Output is correct
7 Correct 8 ms 19168 KB Output is correct
8 Correct 8 ms 19036 KB Output is correct
9 Correct 138 ms 36280 KB Output is correct
10 Correct 14 ms 20992 KB Output is correct
11 Correct 46 ms 28356 KB Output is correct
12 Correct 20 ms 21692 KB Output is correct
13 Correct 31 ms 25296 KB Output is correct
14 Correct 9 ms 19292 KB Output is correct
15 Correct 9 ms 19288 KB Output is correct
16 Correct 135 ms 36276 KB Output is correct
17 Correct 9 ms 19036 KB Output is correct
18 Incorrect 8 ms 19220 KB Tree @(3, 5) appears more than once: for edges on positions 0 and 2
19 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 9 ms 19192 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 9 ms 19124 KB Output is correct
7 Correct 8 ms 19168 KB Output is correct
8 Correct 8 ms 19036 KB Output is correct
9 Correct 138 ms 36280 KB Output is correct
10 Correct 14 ms 20992 KB Output is correct
11 Correct 46 ms 28356 KB Output is correct
12 Correct 20 ms 21692 KB Output is correct
13 Correct 31 ms 25296 KB Output is correct
14 Correct 9 ms 19292 KB Output is correct
15 Correct 9 ms 19288 KB Output is correct
16 Correct 135 ms 36276 KB Output is correct
17 Correct 8 ms 19036 KB Output is correct
18 Correct 8 ms 19204 KB Output is correct
19 Correct 9 ms 19056 KB Output is correct
20 Incorrect 211 ms 53276 KB Tree @(64281, 135721) appears more than once: for edges on positions 91762 and 100001
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 9 ms 19192 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 9 ms 19124 KB Output is correct
7 Correct 8 ms 19168 KB Output is correct
8 Correct 8 ms 19036 KB Output is correct
9 Correct 138 ms 36280 KB Output is correct
10 Correct 14 ms 20992 KB Output is correct
11 Correct 46 ms 28356 KB Output is correct
12 Correct 20 ms 21692 KB Output is correct
13 Correct 31 ms 25296 KB Output is correct
14 Correct 9 ms 19292 KB Output is correct
15 Correct 9 ms 19288 KB Output is correct
16 Correct 135 ms 36276 KB Output is correct
17 Incorrect 262 ms 56232 KB Tree @(100001, 100001) appears more than once: for edges on positions 90476 and 165167
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 9 ms 19192 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 9 ms 19124 KB Output is correct
7 Correct 8 ms 19168 KB Output is correct
8 Correct 8 ms 19036 KB Output is correct
9 Correct 138 ms 36280 KB Output is correct
10 Correct 14 ms 20992 KB Output is correct
11 Correct 46 ms 28356 KB Output is correct
12 Correct 20 ms 21692 KB Output is correct
13 Correct 31 ms 25296 KB Output is correct
14 Correct 9 ms 19292 KB Output is correct
15 Correct 9 ms 19288 KB Output is correct
16 Correct 135 ms 36276 KB Output is correct
17 Correct 9 ms 19036 KB Output is correct
18 Incorrect 8 ms 19220 KB Tree @(3, 5) appears more than once: for edges on positions 0 and 2
19 Halted 0 ms 0 KB -