oj.uz

Submission #1021027

# Submission time Handle Problem Language Result Execution time Memory
1021027 2024-07-12T13:01:59 Z Blistering_Barnacles Fountain Parks (IOI21_parks) C++17
15 / 100
 478 ms 45152 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int construct_roads(vector<int> x, vector<int> y) {
    if (x.size() == 1) {
    build({}, {}, {}, {});
        return 1;
    }
    map<pair<int, int>, int> mp;
    vector<int> u, v, a, b;
    vector<pair<int, int>> e;
    int n = (int)x.size();
    for(int i = 0; i < n; i++){
        if(mp.count({x[i], y[i] - 2})){
            e.push_back({mp[{x[i], y[i] - 2}], i});
        }
        if(mp.count({x[i], y[i] + 2})){
            e.push_back({mp[{x[i], y[i] + 2}], i});
        }
        if(mp.count({x[i] - 2, y[i]})){
            e.push_back({mp[{x[i] - 2, y[i]}], i});
        }
        if(mp.count({x[i] + 2, y[i]})){
            e.push_back({mp[{x[i] + 2, y[i]}], i});
        }
        mp[{x[i], y[i]}] = i;
    }
    vector<int> par(n, -1);
    function<int(int)> getpar = [&](int x){
        return (par[x] < 0 ? x : par[x] = getpar(par[x]));
    };
    auto mrg = [&](int x, int y){
        x = getpar(x), y = getpar(y);
        if(x == y)return false;
        if(par[x] > par[y])swap(x, y);
        par[x] += par[y], par[y] = x;
        return true;
    };
    auto cmp = [&](pair<int, int> a, pair<int, int> b){
        auto [i1, j1] = a;
        auto [i2, j2] = b;
        if(x[i1] == x[j1]){
            if(x[i2] == x[j2]){
                return x[i1] < x[i2];
            }
            else{
                return x[i1] < max(x[i2], x[j2]);
            }
        }
        else{
            if(x[i2] == x[j2]){
                return min(x[i1], x[j1]) < x[i2];
            }
            else{
                return min(x[i1], x[j1]) < min(x[i2], x[j2]);
            }
        }
    };
    sort(e.begin(), e.end(), cmp);
    map<pair<int, int>, bool> vis;
    for(auto [i, j]: e){
        if(mrg(i, j)){
            u.push_back(i), v.push_back(j);
            if(x[i] == x[j]){
                if(!vis.count({x[i] - 1, max(y[i], y[j]) - 1})){
                    vis[{x[i] - 1, max(y[i], y[j]) - 1}] = 1;
                    a.push_back(x[i] - 1);
                    b.push_back(max(y[i], y[j]) - 1);
                }
                else{
                    vis[{x[i] + 1, max(y[i], y[j]) - 1}] = 1;
                    a.push_back(x[i] + 1);
                    b.push_back(max(y[i], y[j]) - 1);
                }
            }
            else{
                if(!vis.count({max(x[i], x[j]) - 1, y[i] - 1})){
                    vis[{max(x[i], x[j]) - 1, y[i] - 1}] = 1;
                    a.push_back(max(x[i], x[j]) - 1);
                    b.push_back(y[i] - 1);
                }
                else{
                    vis[{max(x[i], x[j]) - 1, y[i] + 1}] = 1;
                    a.push_back(max(x[i], x[j]) - 1);
                    b.push_back(y[i] + 1);
                }
            }
        }
    }
    int cnt = 0;
    for(int i = 0; i < n; i++)cnt += par[i] < 0;
    if(cnt > 1)return 0;
    build(u, v, a, b);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 163 ms 21580 KB Output is correct
10 Correct 9 ms 2556 KB Output is correct
11 Correct 71 ms 11640 KB Output is correct
12 Correct 17 ms 3556 KB Output is correct
13 Correct 42 ms 8296 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 3 ms 700 KB Output is correct
16 Correct 149 ms 21664 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 163 ms 21580 KB Output is correct
10 Correct 9 ms 2556 KB Output is correct
11 Correct 71 ms 11640 KB Output is correct
12 Correct 17 ms 3556 KB Output is correct
13 Correct 42 ms 8296 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 3 ms 700 KB Output is correct
16 Correct 149 ms 21664 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 478 ms 43404 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 3 ms 860 KB Output is correct
27 Correct 4 ms 1116 KB Output is correct
28 Correct 152 ms 17560 KB Output is correct
29 Correct 257 ms 25992 KB Output is correct
30 Correct 343 ms 34812 KB Output is correct
31 Correct 436 ms 43272 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 3 ms 604 KB Output is correct
44 Correct 3 ms 844 KB Output is correct
45 Correct 197 ms 21736 KB Output is correct
46 Correct 284 ms 31960 KB Output is correct
47 Correct 279 ms 31944 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 163 ms 21580 KB Output is correct
10 Correct 9 ms 2556 KB Output is correct
11 Correct 71 ms 11640 KB Output is correct
12 Correct 17 ms 3556 KB Output is correct
13 Correct 42 ms 8296 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 3 ms 700 KB Output is correct
16 Correct 149 ms 21664 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 478 ms 43404 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 3 ms 860 KB Output is correct
27 Correct 4 ms 1116 KB Output is correct
28 Correct 152 ms 17560 KB Output is correct
29 Correct 257 ms 25992 KB Output is correct
30 Correct 343 ms 34812 KB Output is correct
31 Correct 436 ms 43272 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 3 ms 604 KB Output is correct
44 Correct 3 ms 844 KB Output is correct
45 Correct 197 ms 21736 KB Output is correct
46 Correct 284 ms 31960 KB Output is correct
47 Correct 279 ms 31944 KB Output is correct
48 Correct 1 ms 348 KB Output is correct
49 Correct 1 ms 348 KB Output is correct
50 Correct 1 ms 436 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 1 ms 344 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 456 ms 43176 KB Output is correct
56 Correct 1 ms 348 KB Output is correct
57 Incorrect 2 ms 604 KB Tree @(5, 185601) appears more than once: for edges on positions 1306 and 1502
58 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 163 ms 21580 KB Output is correct
10 Correct 9 ms 2556 KB Output is correct
11 Correct 71 ms 11640 KB Output is correct
12 Correct 17 ms 3556 KB Output is correct
13 Correct 42 ms 8296 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 3 ms 700 KB Output is correct
16 Correct 149 ms 21664 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 408 ms 45152 KB Output is correct
21 Correct 359 ms 44512 KB Output is correct
22 Correct 388 ms 44656 KB Output is correct
23 Correct 292 ms 37704 KB Output is correct
24 Correct 227 ms 18460 KB Output is correct
25 Correct 349 ms 35780 KB Output is correct
26 Correct 353 ms 35764 KB Output is correct
27 Correct 408 ms 43264 KB Output is correct
28 Correct 396 ms 43264 KB Output is correct
29 Correct 422 ms 43092 KB Output is correct
30 Correct 433 ms 43116 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Incorrect 24 ms 3596 KB Tree @(185725, 20413) appears more than once: for edges on positions 637 and 656
33 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 163 ms 21580 KB Output is correct
10 Correct 9 ms 2556 KB Output is correct
11 Correct 71 ms 11640 KB Output is correct
12 Correct 17 ms 3556 KB Output is correct
13 Correct 42 ms 8296 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 3 ms 700 KB Output is correct
16 Correct 149 ms 21664 KB Output is correct
17 Correct 376 ms 44156 KB Output is correct
18 Correct 346 ms 44408 KB Output is correct
19 Correct 349 ms 44636 KB Output is correct
20 Correct 458 ms 42160 KB Output is correct
21 Correct 397 ms 38196 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Incorrect 51 ms 7476 KB Tree @(185191, 20673) appears more than once: for edges on positions 1202 and 1223
24 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 163 ms 21580 KB Output is correct
10 Correct 9 ms 2556 KB Output is correct
11 Correct 71 ms 11640 KB Output is correct
12 Correct 17 ms 3556 KB Output is correct
13 Correct 42 ms 8296 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 3 ms 700 KB Output is correct
16 Correct 149 ms 21664 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 478 ms 43404 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 3 ms 860 KB Output is correct
27 Correct 4 ms 1116 KB Output is correct
28 Correct 152 ms 17560 KB Output is correct
29 Correct 257 ms 25992 KB Output is correct
30 Correct 343 ms 34812 KB Output is correct
31 Correct 436 ms 43272 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 3 ms 604 KB Output is correct
44 Correct 3 ms 844 KB Output is correct
45 Correct 197 ms 21736 KB Output is correct
46 Correct 284 ms 31960 KB Output is correct
47 Correct 279 ms 31944 KB Output is correct
48 Correct 1 ms 348 KB Output is correct
49 Correct 1 ms 348 KB Output is correct
50 Correct 1 ms 436 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 1 ms 344 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 456 ms 43176 KB Output is correct
56 Correct 1 ms 348 KB Output is correct
57 Incorrect 2 ms 604 KB Tree @(5, 185601) appears more than once: for edges on positions 1306 and 1502
58 Halted 0 ms 0 KB -