oj.uz

Submission #837410

# Submission time Handle Problem Language Result Execution time Memory
837410 2023-08-25T10:34:28 Z QwertyPi Fountain Parks (IOI21_parks) C++17
55 / 100
 1211 ms 84156 KB 
#include "parks.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;

const int N_MAX = 2e5 + 11;

struct point{
    int x, y;
    bool operator< (const point& o) const {
        return x < o.x || (x == o.x && y < o.y);
    }
};

struct edge{
    int u, v;
};

int n;
map<point, int> mp;
vector<point> a;

struct DSU{
    int dsu[N_MAX];
    void init(int n){
        for(int i = 0; i < n; i++) dsu[i] = i;
    }
    int f(int x){ return x == dsu[x] ? x : dsu[x] = f(dsu[x]); }
    void g(int x, int y){ x = f(x), y = f(y); dsu[x] = y; }
} dsu;

vector<edge> construct_tree(){
    vector<edge> ans;
    dsu.init(n);
    for(int i = 0; i < n; i++){
        for(auto [dx, dy] : vector<pair<int, int>>{{0, -2}, {0, 2}, {2, 0}, {-2, 0}}){
            int nx = a[i].x + dx, ny = a[i].y + dy;
            if(mp.count({nx, ny})){
                int v = mp[{nx, ny}];
                if(dsu.f(i) != dsu.f(v)){
                    dsu.g(i, v);
                    ans.push_back({i, v});
                }
            }
        }
    }
    return ans;
}

vector<point> adj(int u, int v){
    assert(abs(a[u].x - a[v].x) + abs(a[u].y - a[v].y) == 2);
    if(a[u].x == a[v].x) return {{a[u].x - 1, (a[u].y + a[v].y) / 2}, {a[u].x + 1, (a[u].y + a[v].y) / 2}};
    else return {{(a[u].x + a[v].x) / 2, a[v].y - 1}, {(a[u].x + a[v].x) / 2, a[v].y + 1}};
}

vector<point> assign_benches(vector<edge> roads){
    vector<point> ans(roads.size());
    map<point, vector<int>> deg;
    set<point> done;
    for(int i = 0; i < (int) roads.size(); i++){
        int u = roads[i].u, v = roads[i].v;
        vector<point> p = adj(u, v);
        deg[p[0]].push_back(i);
        deg[p[1]].push_back(i);
    }
    vector<point> deg_0, deg_1;
    for(auto [p, v] : deg){
        if(v.size() == 0) deg_0.push_back(p);
        if(v.size() == 1) deg_1.push_back(p);
    }
    while(deg.size()){
        while(deg_0.size()) deg.erase(deg_0.back()), deg_0.pop_back();
        while(deg_1.size()){
            point v = deg_1.back(); deg_1.pop_back();
            if(done.count(v) || deg[v].empty()) continue; done.insert(v);

            int r = deg[v][0];
            ans[r] = v;

            int a = roads[r].u, b = roads[r].v;
            vector<point> p = adj(a, b);
            if(find(all(deg[p[0]]), r) != deg[p[0]].end()) deg[p[0]].erase(find(all(deg[p[0]]), r));
            if(find(all(deg[p[1]]), r) != deg[p[1]].end()) deg[p[1]].erase(find(all(deg[p[1]]), r));

            if(deg.count(p[0]) && deg[p[0]].size() == 0) deg_0.push_back(p[0]);
            if(deg.count(p[0]) && deg[p[0]].size() == 1) deg_1.push_back(p[0]);

            if(deg.count(p[1]) && deg[p[1]].size() == 0) deg_0.push_back(p[1]);
            if(deg.count(p[1]) && deg[p[1]].size() == 1) deg_1.push_back(p[1]);
        }
        if(deg.size()){
            auto [c, v] = *deg.begin(); 
            if(done.count(c) || deg[c].size() < 2){
                deg.erase(deg.begin());
                continue;
            }
            done.insert(c);
            int r = v[0];
            ans[r] = c;

            int a = roads[r].u, b = roads[r].v;
            vector<point> p = adj(a, b);

            deg[p[0]].clear();
            if(find(all(deg[p[1]]), r) != deg[p[1]].end()) deg[p[1]].erase(find(all(deg[p[1]]), r));

            if(deg[p[0]].size() == 0) deg_0.push_back(p[0]);
            if(deg[p[0]].size() == 1) deg_1.push_back(p[0]);

            if(deg[p[1]].size() == 0) deg_0.push_back(p[1]);
            if(deg[p[1]].size() == 1) deg_1.push_back(p[1]);
        }
    }
    return ans;
}

int construct_roads(vector<int> x, vector<int> y) {
    n = x.size();
    for(int i = 0; i < n; i++){
        a.push_back({x[i], y[i]});
        mp[a[i]] = i;
    }

    vector<edge> edges = construct_tree();
    if((int) edges.size() < n - 1) return 0;
    vector<point> benches = assign_benches(edges);
    vector<int> u(n - 1), v(n - 1), a(n - 1), b(n - 1);
    for(int i = 0; i < n - 1; i++){
        u[i] = edges[i].u, v[i] = edges[i].v;
        a[i] = benches[i].x, b[i] = benches[i].y;
    }
    build(u, v, a, b);
    return 1;
}

Compilation message

parks.cpp: In function 'std::vector<point> assign_benches(std::vector<edge>)':
parks.cpp:75:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   75 |             if(done.count(v) || deg[v].empty()) continue; done.insert(v);
      |             ^~
parks.cpp:75:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   75 |             if(done.count(v) || deg[v].empty()) continue; done.insert(v);
      |                                                           ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 476 ms 41312 KB Output is correct
10 Correct 33 ms 4440 KB Output is correct
11 Correct 234 ms 22452 KB Output is correct
12 Correct 52 ms 6464 KB Output is correct
13 Correct 34 ms 5060 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 478 ms 41328 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 476 ms 41312 KB Output is correct
10 Correct 33 ms 4440 KB Output is correct
11 Correct 234 ms 22452 KB Output is correct
12 Correct 52 ms 6464 KB Output is correct
13 Correct 34 ms 5060 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 478 ms 41328 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1139 ms 62940 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 4 ms 596 KB Output is correct
26 Correct 3 ms 596 KB Output is correct
27 Correct 4 ms 724 KB Output is correct
28 Correct 363 ms 25452 KB Output is correct
29 Correct 590 ms 38008 KB Output is correct
30 Correct 850 ms 50364 KB Output is correct
31 Correct 1136 ms 63264 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 2 ms 516 KB Output is correct
44 Correct 3 ms 596 KB Output is correct
45 Correct 471 ms 33856 KB Output is correct
46 Correct 765 ms 47956 KB Output is correct
47 Correct 760 ms 47928 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 476 ms 41312 KB Output is correct
10 Correct 33 ms 4440 KB Output is correct
11 Correct 234 ms 22452 KB Output is correct
12 Correct 52 ms 6464 KB Output is correct
13 Correct 34 ms 5060 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 478 ms 41328 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1139 ms 62940 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 4 ms 596 KB Output is correct
26 Correct 3 ms 596 KB Output is correct
27 Correct 4 ms 724 KB Output is correct
28 Correct 363 ms 25452 KB Output is correct
29 Correct 590 ms 38008 KB Output is correct
30 Correct 850 ms 50364 KB Output is correct
31 Correct 1136 ms 63264 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 2 ms 516 KB Output is correct
44 Correct 3 ms 596 KB Output is correct
45 Correct 471 ms 33856 KB Output is correct
46 Correct 765 ms 47956 KB Output is correct
47 Correct 760 ms 47928 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 0 ms 212 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 0 ms 212 KB Output is correct
54 Correct 1 ms 212 KB Output is correct
55 Incorrect 1066 ms 58664 KB a[165] = 0 is not an odd integer
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 476 ms 41312 KB Output is correct
10 Correct 33 ms 4440 KB Output is correct
11 Correct 234 ms 22452 KB Output is correct
12 Correct 52 ms 6464 KB Output is correct
13 Correct 34 ms 5060 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 478 ms 41328 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 911 ms 55808 KB Output is correct
21 Correct 987 ms 55948 KB Output is correct
22 Correct 985 ms 55868 KB Output is correct
23 Correct 889 ms 70348 KB Output is correct
24 Correct 275 ms 18236 KB Output is correct
25 Correct 376 ms 21308 KB Output is correct
26 Correct 362 ms 21300 KB Output is correct
27 Correct 1141 ms 82372 KB Output is correct
28 Correct 1211 ms 82484 KB Output is correct
29 Correct 1186 ms 82372 KB Output is correct
30 Correct 1192 ms 82308 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 53 ms 4736 KB Output is correct
33 Correct 91 ms 10560 KB Output is correct
34 Correct 898 ms 58380 KB Output is correct
35 Correct 11 ms 1492 KB Output is correct
36 Correct 66 ms 6084 KB Output is correct
37 Correct 149 ms 11996 KB Output is correct
38 Correct 380 ms 24916 KB Output is correct
39 Correct 516 ms 34108 KB Output is correct
40 Correct 714 ms 43920 KB Output is correct
41 Correct 906 ms 52752 KB Output is correct
42 Correct 1151 ms 61820 KB Output is correct
43 Correct 1 ms 212 KB Output is correct
44 Correct 0 ms 212 KB Output is correct
45 Correct 0 ms 212 KB Output is correct
46 Correct 1 ms 212 KB Output is correct
47 Correct 0 ms 212 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 0 ms 212 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 0 ms 212 KB Output is correct
54 Correct 2 ms 468 KB Output is correct
55 Correct 3 ms 596 KB Output is correct
56 Correct 463 ms 34728 KB Output is correct
57 Correct 744 ms 49080 KB Output is correct
58 Correct 746 ms 49208 KB Output is correct
59 Correct 1 ms 336 KB Output is correct
60 Correct 0 ms 212 KB Output is correct
61 Correct 0 ms 212 KB Output is correct
62 Correct 1116 ms 84092 KB Output is correct
63 Correct 1108 ms 84156 KB Output is correct
64 Correct 1097 ms 83644 KB Output is correct
65 Correct 4 ms 724 KB Output is correct
66 Correct 8 ms 1108 KB Output is correct
67 Correct 478 ms 32944 KB Output is correct
68 Correct 806 ms 49488 KB Output is correct
69 Correct 1176 ms 65760 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 476 ms 41312 KB Output is correct
10 Correct 33 ms 4440 KB Output is correct
11 Correct 234 ms 22452 KB Output is correct
12 Correct 52 ms 6464 KB Output is correct
13 Correct 34 ms 5060 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 478 ms 41328 KB Output is correct
17 Correct 1091 ms 82432 KB Output is correct
18 Correct 1083 ms 82500 KB Output is correct
19 Correct 986 ms 58228 KB Output is correct
20 Correct 1016 ms 55812 KB Output is correct
21 Correct 933 ms 62488 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 133 ms 10452 KB Output is correct
24 Correct 25 ms 2640 KB Output is correct
25 Correct 101 ms 9024 KB Output is correct
26 Correct 199 ms 14020 KB Output is correct
27 Correct 483 ms 31720 KB Output is correct
28 Correct 627 ms 40392 KB Output is correct
29 Correct 799 ms 47548 KB Output is correct
30 Correct 980 ms 54968 KB Output is correct
31 Correct 1144 ms 63140 KB Output is correct
32 Correct 1125 ms 70272 KB Output is correct
33 Correct 1137 ms 84084 KB Output is correct
34 Correct 5 ms 976 KB Output is correct
35 Correct 9 ms 1312 KB Output is correct
36 Correct 481 ms 33104 KB Output is correct
37 Correct 778 ms 49728 KB Output is correct
38 Correct 1203 ms 66212 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 476 ms 41312 KB Output is correct
10 Correct 33 ms 4440 KB Output is correct
11 Correct 234 ms 22452 KB Output is correct
12 Correct 52 ms 6464 KB Output is correct
13 Correct 34 ms 5060 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 478 ms 41328 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1139 ms 62940 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 4 ms 596 KB Output is correct
26 Correct 3 ms 596 KB Output is correct
27 Correct 4 ms 724 KB Output is correct
28 Correct 363 ms 25452 KB Output is correct
29 Correct 590 ms 38008 KB Output is correct
30 Correct 850 ms 50364 KB Output is correct
31 Correct 1136 ms 63264 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 2 ms 516 KB Output is correct
44 Correct 3 ms 596 KB Output is correct
45 Correct 471 ms 33856 KB Output is correct
46 Correct 765 ms 47956 KB Output is correct
47 Correct 760 ms 47928 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 0 ms 212 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 0 ms 212 KB Output is correct
54 Correct 1 ms 212 KB Output is correct
55 Incorrect 1066 ms 58664 KB a[165] = 0 is not an odd integer
56 Halted 0 ms 0 KB -