oj.uz

Submission #443432

# Submission time Handle Problem Language Result Execution time Memory
443432 2021-07-10T13:29:02 Z mjhmjh1104 Fountain Parks (IOI21_parks) C++17
5 / 100
 758 ms 42828 KB 
#include "parks.h"
#include <map>
#include <set>
#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++) points.push_back(i);
    sort(points.begin(), points.end(), [&](const int &a, const int &b) {
        return y[a] < y[b];
    });
    for (int t = 0; t < n; 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;
    for (auto &i: edges) if (x[i.first] == 2 && x[i.first] == 2) {
        u.push_back(i.first);
        v.push_back(i.second);
        a.push_back(1);
        b.push_back((y[i.first] + y[i.second]) / 2);
        s.insert({ a.back(), b.back() });
    } else if (x[i.first] == 6 && x[i.second] == 6) {
        u.push_back(i.first);
        v.push_back(i.second);
        a.push_back(7);
        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) {
        return min(y[a.first], y[a.second]) < min(y[b.first], y[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 {
                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 {
                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 284 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 288 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 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 236 ms 20468 KB Output is correct
10 Correct 13 ms 2508 KB Output is correct
11 Correct 78 ms 11804 KB Output is correct
12 Correct 21 ms 3664 KB Output is correct
13 Correct 41 ms 5452 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 222 ms 20484 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 288 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 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 236 ms 20468 KB Output is correct
10 Correct 13 ms 2508 KB Output is correct
11 Correct 78 ms 11804 KB Output is correct
12 Correct 21 ms 3664 KB Output is correct
13 Correct 41 ms 5452 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 222 ms 20484 KB Output is correct
17 Incorrect 0 ms 204 KB b[1] = 2 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 288 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 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 236 ms 20468 KB Output is correct
10 Correct 13 ms 2508 KB Output is correct
11 Correct 78 ms 11804 KB Output is correct
12 Correct 21 ms 3664 KB Output is correct
13 Correct 41 ms 5452 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 222 ms 20484 KB Output is correct
17 Incorrect 0 ms 204 KB b[1] = 2 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 288 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 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 236 ms 20468 KB Output is correct
10 Correct 13 ms 2508 KB Output is correct
11 Correct 78 ms 11804 KB Output is correct
12 Correct 21 ms 3664 KB Output is correct
13 Correct 41 ms 5452 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 222 ms 20484 KB Output is correct
17 Correct 1 ms 288 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Incorrect 591 ms 42828 KB Tree @(7, 199997) appears more than once: for edges on positions 0 and 199994
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 288 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 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 236 ms 20468 KB Output is correct
10 Correct 13 ms 2508 KB Output is correct
11 Correct 78 ms 11804 KB Output is correct
12 Correct 21 ms 3664 KB Output is correct
13 Correct 41 ms 5452 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 222 ms 20484 KB Output is correct
17 Incorrect 758 ms 40272 KB b[50000] = 2 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 284 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 288 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 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 236 ms 20468 KB Output is correct
10 Correct 13 ms 2508 KB Output is correct
11 Correct 78 ms 11804 KB Output is correct
12 Correct 21 ms 3664 KB Output is correct
13 Correct 41 ms 5452 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 222 ms 20484 KB Output is correct
17 Incorrect 0 ms 204 KB b[1] = 2 is not an odd integer
18 Halted 0 ms 0 KB -