oj.uz

Submission #443448

# Submission time Handle Problem Language Result Execution time Memory
443448 2021-07-10T13:56:35 Z mjhmjh1104 Fountain Parks (IOI21_parks) C++17
5 / 100
 746 ms 41344 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);
            }
        }
        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 0 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 270 ms 19220 KB Output is correct
10 Correct 14 ms 2380 KB Output is correct
11 Correct 77 ms 11112 KB Output is correct
12 Correct 20 ms 3420 KB Output is correct
13 Correct 38 ms 4808 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 265 ms 19244 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 0 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 270 ms 19220 KB Output is correct
10 Correct 14 ms 2380 KB Output is correct
11 Correct 77 ms 11112 KB Output is correct
12 Correct 20 ms 3420 KB Output is correct
13 Correct 38 ms 4808 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 265 ms 19244 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 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 675 ms 38384 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 3 ms 588 KB Output is correct
27 Correct 4 ms 588 KB Output is correct
28 Correct 176 ms 15488 KB Output is correct
29 Correct 342 ms 23004 KB Output is correct
30 Correct 505 ms 31224 KB Output is correct
31 Correct 668 ms 38384 KB Output is correct
32 Correct 0 ms 204 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 0 ms 204 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 0 ms 280 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 1 ms 204 KB Output is correct
43 Correct 2 ms 460 KB Output is correct
44 Correct 3 ms 588 KB Output is correct
45 Incorrect 210 ms 14776 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 0 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 270 ms 19220 KB Output is correct
10 Correct 14 ms 2380 KB Output is correct
11 Correct 77 ms 11112 KB Output is correct
12 Correct 20 ms 3420 KB Output is correct
13 Correct 38 ms 4808 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 265 ms 19244 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 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 675 ms 38384 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 3 ms 588 KB Output is correct
27 Correct 4 ms 588 KB Output is correct
28 Correct 176 ms 15488 KB Output is correct
29 Correct 342 ms 23004 KB Output is correct
30 Correct 505 ms 31224 KB Output is correct
31 Correct 668 ms 38384 KB Output is correct
32 Correct 0 ms 204 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 0 ms 204 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 0 ms 280 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 1 ms 204 KB Output is correct
43 Correct 2 ms 460 KB Output is correct
44 Correct 3 ms 588 KB Output is correct
45 Incorrect 210 ms 14776 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 0 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 270 ms 19220 KB Output is correct
10 Correct 14 ms 2380 KB Output is correct
11 Correct 77 ms 11112 KB Output is correct
12 Correct 20 ms 3420 KB Output is correct
13 Correct 38 ms 4808 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 265 ms 19244 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 711 ms 41344 KB Output is correct
21 Correct 708 ms 39924 KB Output is correct
22 Correct 746 ms 40596 KB Output is correct
23 Correct 535 ms 34100 KB Output is correct
24 Correct 481 ms 17840 KB Output is correct
25 Correct 639 ms 19652 KB Output is correct
26 Correct 485 ms 18880 KB Output is correct
27 Correct 687 ms 38408 KB Output is correct
28 Correct 707 ms 38564 KB Output is correct
29 Correct 736 ms 39564 KB Output is correct
30 Incorrect 643 ms 22184 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 0 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 270 ms 19220 KB Output is correct
10 Correct 14 ms 2380 KB Output is correct
11 Correct 77 ms 11112 KB Output is correct
12 Correct 20 ms 3420 KB Output is correct
13 Correct 38 ms 4808 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 265 ms 19244 KB Output is correct
17 Correct 710 ms 39956 KB Output is correct
18 Correct 687 ms 40188 KB Output is correct
19 Incorrect 670 ms 30272 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 0 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 270 ms 19220 KB Output is correct
10 Correct 14 ms 2380 KB Output is correct
11 Correct 77 ms 11112 KB Output is correct
12 Correct 20 ms 3420 KB Output is correct
13 Correct 38 ms 4808 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 265 ms 19244 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 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 675 ms 38384 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 3 ms 588 KB Output is correct
27 Correct 4 ms 588 KB Output is correct
28 Correct 176 ms 15488 KB Output is correct
29 Correct 342 ms 23004 KB Output is correct
30 Correct 505 ms 31224 KB Output is correct
31 Correct 668 ms 38384 KB Output is correct
32 Correct 0 ms 204 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 0 ms 204 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 0 ms 280 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 1 ms 204 KB Output is correct
43 Correct 2 ms 460 KB Output is correct
44 Correct 3 ms 588 KB Output is correct
45 Incorrect 210 ms 14776 KB Solution announced impossible, but it is possible.
46 Halted 0 ms 0 KB -