oj.uz

Submission #1021410

# Submission time Handle Problem Language Result Execution time Memory
1021410 2024-07-12T17:39:22 Z Wael Fountain Parks (IOI21_parks) C++17
5 / 100
 191 ms 41400 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 + 1);
    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 (x[i] == 4) {
            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 19032 KB Output is correct
2 Correct 8 ms 19124 KB Output is correct
3 Correct 10 ms 19188 KB Output is correct
4 Correct 9 ms 19032 KB Output is correct
5 Correct 9 ms 19036 KB Output is correct
6 Correct 9 ms 19032 KB Output is correct
7 Correct 9 ms 19036 KB Output is correct
8 Correct 8 ms 19108 KB Output is correct
9 Correct 152 ms 36456 KB Output is correct
10 Correct 16 ms 20828 KB Output is correct
11 Correct 50 ms 28368 KB Output is correct
12 Correct 19 ms 21596 KB Output is correct
13 Correct 34 ms 25284 KB Output is correct
14 Correct 10 ms 19288 KB Output is correct
15 Correct 10 ms 19404 KB Output is correct
16 Correct 150 ms 36280 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19032 KB Output is correct
2 Correct 8 ms 19124 KB Output is correct
3 Correct 10 ms 19188 KB Output is correct
4 Correct 9 ms 19032 KB Output is correct
5 Correct 9 ms 19036 KB Output is correct
6 Correct 9 ms 19032 KB Output is correct
7 Correct 9 ms 19036 KB Output is correct
8 Correct 8 ms 19108 KB Output is correct
9 Correct 152 ms 36456 KB Output is correct
10 Correct 16 ms 20828 KB Output is correct
11 Correct 50 ms 28368 KB Output is correct
12 Correct 19 ms 21596 KB Output is correct
13 Correct 34 ms 25284 KB Output is correct
14 Correct 10 ms 19288 KB Output is correct
15 Correct 10 ms 19404 KB Output is correct
16 Correct 150 ms 36280 KB Output is correct
17 Correct 9 ms 19032 KB Output is correct
18 Incorrect 9 ms 19036 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 19032 KB Output is correct
2 Correct 8 ms 19124 KB Output is correct
3 Correct 10 ms 19188 KB Output is correct
4 Correct 9 ms 19032 KB Output is correct
5 Correct 9 ms 19036 KB Output is correct
6 Correct 9 ms 19032 KB Output is correct
7 Correct 9 ms 19036 KB Output is correct
8 Correct 8 ms 19108 KB Output is correct
9 Correct 152 ms 36456 KB Output is correct
10 Correct 16 ms 20828 KB Output is correct
11 Correct 50 ms 28368 KB Output is correct
12 Correct 19 ms 21596 KB Output is correct
13 Correct 34 ms 25284 KB Output is correct
14 Correct 10 ms 19288 KB Output is correct
15 Correct 10 ms 19404 KB Output is correct
16 Correct 150 ms 36280 KB Output is correct
17 Correct 9 ms 19032 KB Output is correct
18 Incorrect 9 ms 19036 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 19032 KB Output is correct
2 Correct 8 ms 19124 KB Output is correct
3 Correct 10 ms 19188 KB Output is correct
4 Correct 9 ms 19032 KB Output is correct
5 Correct 9 ms 19036 KB Output is correct
6 Correct 9 ms 19032 KB Output is correct
7 Correct 9 ms 19036 KB Output is correct
8 Correct 8 ms 19108 KB Output is correct
9 Correct 152 ms 36456 KB Output is correct
10 Correct 16 ms 20828 KB Output is correct
11 Correct 50 ms 28368 KB Output is correct
12 Correct 19 ms 21596 KB Output is correct
13 Correct 34 ms 25284 KB Output is correct
14 Correct 10 ms 19288 KB Output is correct
15 Correct 10 ms 19404 KB Output is correct
16 Correct 150 ms 36280 KB Output is correct
17 Runtime error 23 ms 38492 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19032 KB Output is correct
2 Correct 8 ms 19124 KB Output is correct
3 Correct 10 ms 19188 KB Output is correct
4 Correct 9 ms 19032 KB Output is correct
5 Correct 9 ms 19036 KB Output is correct
6 Correct 9 ms 19032 KB Output is correct
7 Correct 9 ms 19036 KB Output is correct
8 Correct 8 ms 19108 KB Output is correct
9 Correct 152 ms 36456 KB Output is correct
10 Correct 16 ms 20828 KB Output is correct
11 Correct 50 ms 28368 KB Output is correct
12 Correct 19 ms 21596 KB Output is correct
13 Correct 34 ms 25284 KB Output is correct
14 Correct 10 ms 19288 KB Output is correct
15 Correct 10 ms 19404 KB Output is correct
16 Correct 150 ms 36280 KB Output is correct
17 Incorrect 191 ms 41400 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19032 KB Output is correct
2 Correct 8 ms 19124 KB Output is correct
3 Correct 10 ms 19188 KB Output is correct
4 Correct 9 ms 19032 KB Output is correct
5 Correct 9 ms 19036 KB Output is correct
6 Correct 9 ms 19032 KB Output is correct
7 Correct 9 ms 19036 KB Output is correct
8 Correct 8 ms 19108 KB Output is correct
9 Correct 152 ms 36456 KB Output is correct
10 Correct 16 ms 20828 KB Output is correct
11 Correct 50 ms 28368 KB Output is correct
12 Correct 19 ms 21596 KB Output is correct
13 Correct 34 ms 25284 KB Output is correct
14 Correct 10 ms 19288 KB Output is correct
15 Correct 10 ms 19404 KB Output is correct
16 Correct 150 ms 36280 KB Output is correct
17 Correct 9 ms 19032 KB Output is correct
18 Incorrect 9 ms 19036 KB Tree @(3, 5) appears more than once: for edges on positions 0 and 2
19 Halted 0 ms 0 KB -