oj.uz

Submission #443449

# Submission time Handle Problem Language Result Execution time Memory
443449 2021-07-10T14:03:28 Z mjhmjh1104 Fountain Parks (IOI21_parks) C++17
5 / 100
 770 ms 40300 KB 
#include "parks.h"
#include <map>
#include <set>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int uf[200006];

int _find(int x) {
    if (uf[x] == -1) return x;
    return uf[x] = _find(uf[x]);
}

void _merge(int x, int y) {
    x = _find(x), y = _find(y);
    if (x != y) uf[x] = y;
}

map<pair<int, int>, int> m;
set<pair<int, int>> s;

int construct_roads(vector<int> x, vector<int> y) {
    if ((int)x.size() == 1) return build({}, {}, {}, {}), 1;
    int n = (int)x.size();
    for (int i = 0; i < n; i++) uf[i] = -1;
    vector<int> u, v, a, b;
    vector<pair<int, int>> edges, n_edges;
    vector<int> points;
    for (int i = 0; i < n; i++) m[{ x[i], y[i] }] = i;
    for (int i = 0; i < n; i++) if (m.count({ x[i], y[i] - 2 })) {
        edges.push_back({ m[{ x[i], y[i] - 2 }], i });
        _merge(edges.back().first, edges.back().second);
    }
    for (int i = 0; i < n; i++) if (!m.count({ x[i], y[i] - 2 }) || !m.count({ x[i], y[i] + 2 })) points.push_back(i);
    sort(points.begin(), points.end(), [&](const int &a, const int &b) {
        if (y[a] != y[b]) return y[a] < y[b];
        return x[a] < x[b];
    });
    for (int t = 0; t < (int)points.size(); t++) {
        int i = points[t];
        if (m.count({ x[i] - 2, y[i] })) {
            int t = m[{ x[i] - 2, y[i] }];
            if (_find(t) != _find(i)) {
                edges.push_back({ t, i });
                _merge(t, i);
            }
        }
    }
    for (int i = 1; i < n; i++) if (_find(0) != _find(i)) return 0;
    //int min_x = *min_element(x.begin(), x.end()), max_x = *max_element(x.begin(), x.end());
    for (auto &i: edges) {
        /*if (x[i.first] == x[i.second]) {
            u.push_back(i.first);
            v.push_back(i.second);
            a.push_back(x[i.first] - 1);
            b.push_back((y[i.first] + y[i.second]) / 2);
            s.insert({ a.back(), b.back() });
        } else*/ n_edges.push_back(i);
    }
    sort(n_edges.begin(), n_edges.end(), [&](const pair<int, int> &a, const pair<int, int> &b) {
        if (min(y[a.first], y[a.second]) != min(y[b.first], y[b.second])) return min(y[a.first], y[a.second]) < min(y[b.first], y[b.second]);
        return min(x[a.first], x[a.second]) < min(x[b.first], x[b.second]);
    });
    for (auto &i: n_edges) {
        if (x[i.first] == x[i.second]) {
            if (!s.count({ x[i.first] - 1, (y[i.first] + y[i.second]) / 2 })) {
                s.insert({ x[i.first] - 1, (y[i.first] + y[i.second]) / 2 });
                u.push_back(i.first);
                v.push_back(i.second);
                a.push_back(x[i.first] - 1);
                b.push_back((y[i.first] + y[i.second]) / 2);
            } else {
                if (s.count({ x[i.first] + 1, (y[i.first] + y[i.second]) / 2 })) return 0;
                s.insert({ x[i.first] + 1, (y[i.first] + y[i.second]) / 2 });
                u.push_back(i.first);
                v.push_back(i.second);
                a.push_back(x[i.first] + 1);
                b.push_back((y[i.first] + y[i.second]) / 2);
            }
        } else {
            if (!s.count({ (x[i.first] + x[i.second]) / 2, y[i.first] - 1 })) {
                s.insert({ (x[i.first] + x[i.second]) / 2, y[i.first] - 1 });
                u.push_back(i.first);
                v.push_back(i.second);
                a.push_back((x[i.first] + x[i.second]) / 2);
                b.push_back(y[i.first] - 1);
            } else {
                if (s.count({ (x[i.first] + x[i.second]) / 2, y[i.first] + 1 })) return 0;
                s.insert({ (x[i.first] + x[i.second]) / 2, y[i.first] + 1 });
                u.push_back(i.first);
                v.push_back(i.second);
                a.push_back((x[i.first] + x[i.second]) / 2);
                b.push_back(y[i.first] + 1);
            }
        }
    }
    build(u, v, a, b);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 271 ms 19480 KB Output is correct
10 Correct 17 ms 2508 KB Output is correct
11 Correct 86 ms 11340 KB Output is correct
12 Correct 21 ms 3628 KB Output is correct
13 Correct 38 ms 4676 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 321 ms 19620 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 271 ms 19480 KB Output is correct
10 Correct 17 ms 2508 KB Output is correct
11 Correct 86 ms 11340 KB Output is correct
12 Correct 21 ms 3628 KB Output is correct
13 Correct 38 ms 4676 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 321 ms 19620 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 734 ms 38828 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 3 ms 460 KB Output is correct
27 Correct 4 ms 668 KB Output is correct
28 Correct 209 ms 15840 KB Output is correct
29 Correct 427 ms 23360 KB Output is correct
30 Correct 531 ms 31384 KB Output is correct
31 Correct 706 ms 38804 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 0 ms 204 KB Output is correct
37 Correct 0 ms 204 KB Output is correct
38 Correct 0 ms 204 KB Output is correct
39 Correct 0 ms 204 KB Output is correct
40 Correct 0 ms 204 KB Output is correct
41 Correct 0 ms 204 KB Output is correct
42 Correct 0 ms 204 KB Output is correct
43 Correct 2 ms 460 KB Output is correct
44 Correct 3 ms 460 KB Output is correct
45 Incorrect 178 ms 9632 KB Solution announced impossible, but it is possible.
46 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 271 ms 19480 KB Output is correct
10 Correct 17 ms 2508 KB Output is correct
11 Correct 86 ms 11340 KB Output is correct
12 Correct 21 ms 3628 KB Output is correct
13 Correct 38 ms 4676 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 321 ms 19620 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 734 ms 38828 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 3 ms 460 KB Output is correct
27 Correct 4 ms 668 KB Output is correct
28 Correct 209 ms 15840 KB Output is correct
29 Correct 427 ms 23360 KB Output is correct
30 Correct 531 ms 31384 KB Output is correct
31 Correct 706 ms 38804 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 0 ms 204 KB Output is correct
37 Correct 0 ms 204 KB Output is correct
38 Correct 0 ms 204 KB Output is correct
39 Correct 0 ms 204 KB Output is correct
40 Correct 0 ms 204 KB Output is correct
41 Correct 0 ms 204 KB Output is correct
42 Correct 0 ms 204 KB Output is correct
43 Correct 2 ms 460 KB Output is correct
44 Correct 3 ms 460 KB Output is correct
45 Incorrect 178 ms 9632 KB Solution announced impossible, but it is possible.
46 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 271 ms 19480 KB Output is correct
10 Correct 17 ms 2508 KB Output is correct
11 Correct 86 ms 11340 KB Output is correct
12 Correct 21 ms 3628 KB Output is correct
13 Correct 38 ms 4676 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 321 ms 19620 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 759 ms 39612 KB Output is correct
21 Correct 736 ms 40300 KB Output is correct
22 Correct 728 ms 39752 KB Output is correct
23 Correct 544 ms 34216 KB Output is correct
24 Correct 522 ms 17864 KB Output is correct
25 Correct 580 ms 19804 KB Output is correct
26 Correct 483 ms 18880 KB Output is correct
27 Correct 756 ms 38972 KB Output is correct
28 Correct 770 ms 38952 KB Output is correct
29 Correct 729 ms 39764 KB Output is correct
30 Incorrect 530 ms 19772 KB Solution announced impossible, but it is possible.
31 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 271 ms 19480 KB Output is correct
10 Correct 17 ms 2508 KB Output is correct
11 Correct 86 ms 11340 KB Output is correct
12 Correct 21 ms 3628 KB Output is correct
13 Correct 38 ms 4676 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 321 ms 19620 KB Output is correct
17 Correct 668 ms 39904 KB Output is correct
18 Correct 687 ms 39692 KB Output is correct
19 Incorrect 539 ms 19768 KB Solution announced impossible, but it is possible.
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 271 ms 19480 KB Output is correct
10 Correct 17 ms 2508 KB Output is correct
11 Correct 86 ms 11340 KB Output is correct
12 Correct 21 ms 3628 KB Output is correct
13 Correct 38 ms 4676 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 321 ms 19620 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 734 ms 38828 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 3 ms 460 KB Output is correct
27 Correct 4 ms 668 KB Output is correct
28 Correct 209 ms 15840 KB Output is correct
29 Correct 427 ms 23360 KB Output is correct
30 Correct 531 ms 31384 KB Output is correct
31 Correct 706 ms 38804 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 0 ms 204 KB Output is correct
37 Correct 0 ms 204 KB Output is correct
38 Correct 0 ms 204 KB Output is correct
39 Correct 0 ms 204 KB Output is correct
40 Correct 0 ms 204 KB Output is correct
41 Correct 0 ms 204 KB Output is correct
42 Correct 0 ms 204 KB Output is correct
43 Correct 2 ms 460 KB Output is correct
44 Correct 3 ms 460 KB Output is correct
45 Incorrect 178 ms 9632 KB Solution announced impossible, but it is possible.
46 Halted 0 ms 0 KB -