oj.uz

Submission #1026321

# Submission time Handle Problem Language Result Execution time Memory
1026321 2024-07-17T22:27:03 Z HappyCapybara Fountain Parks (IOI21_parks) C++17
15 / 100
 217 ms 49940 KB 
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;

vector<int> p;

int find(int a){
    if (p[a] == a) return a;
    else return p[a] = find(p[a]);
}

void merge(int a, int b){
    a = find(a);
    b = find(b);
    if (a == b) return;
    p[a] = b;
}

int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    unordered_map<int,vector<pair<int,int>>> r, c;
    for (int i=0; i<n; i++){
        r[y[i]].push_back({x[i], i});
        c[x[i]].push_back({y[i], i});
    }
    vector<pair<int,int>> el;
    //cout << "a\n";
    for (int i=2; i<=200000; i++){
        if (c[i].size() > 1){
            sort(c[i].begin(), c[i].end());
            for (int j=0; j<c[i].size()-1; j++){
                if (c[i][j+1].first-c[i][j].first == 2) el.push_back({c[i][j].second, c[i][j+1].second});
            }
        }
        if (r[i].size() > 1){
            sort(r[i].begin(), r[i].end());
            for (int j=0; j<r[i].size()-1; j++){
                if (r[i][j+1].first-r[i][j].first == 2) el.push_back({r[i][j].second, r[i][j+1].second});
            }
        }
    }
    p.resize(n);
    for (int i=0; i<n; i++) p[i] = i;
    //cout << "b\n";
    vector<int> u, v, a, b;
    int done = 0;
    int cur = -1;
    while (done < n-1){
        cur++;
        //cout << cur << " " << done << "\n";
        if (cur == el.size()) return 0;
        if (find(el[cur].first) == find(el[cur].second)) continue;
        //cout << "a\n";
        merge(el[cur].first, el[cur].second);
        done++;
        u.push_back(el[cur].first);
        v.push_back(el[cur].second);
        //cout << "b\n";
        if (x[el[cur].first] == x[el[cur].second]){
            b.push_back((y[el[cur].first]+y[el[cur].second])/2);
            if (x[el[cur].first] == 2) a.push_back(1);
            else a.push_back(x[el[cur].first]+1);
        }
        else {
            a.push_back((x[el[cur].first]+x[el[cur].second])/2);
            b.push_back(y[el[cur].first]-1);
        }
        //cout << "c\n";
    }
    //cout << "c\n";
    build(u, v, a, b);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:31:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             for (int j=0; j<c[i].size()-1; j++){
      |                           ~^~~~~~~~~~~~~~
parks.cpp:37:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for (int j=0; j<r[i].size()-1; j++){
      |                           ~^~~~~~~~~~~~~~
parks.cpp:51:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         if (cur == el.size()) return 0;
      |             ~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24492 KB Output is correct
2 Correct 26 ms 24500 KB Output is correct
3 Correct 25 ms 24492 KB Output is correct
4 Correct 26 ms 24500 KB Output is correct
5 Correct 27 ms 24500 KB Output is correct
6 Correct 26 ms 24500 KB Output is correct
7 Correct 28 ms 24500 KB Output is correct
8 Correct 28 ms 24500 KB Output is correct
9 Correct 89 ms 37292 KB Output is correct
10 Correct 31 ms 25932 KB Output is correct
11 Correct 61 ms 31252 KB Output is correct
12 Correct 31 ms 26384 KB Output is correct
13 Correct 44 ms 29204 KB Output is correct
14 Correct 28 ms 24756 KB Output is correct
15 Correct 28 ms 24756 KB Output is correct
16 Correct 76 ms 37220 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24492 KB Output is correct
2 Correct 26 ms 24500 KB Output is correct
3 Correct 25 ms 24492 KB Output is correct
4 Correct 26 ms 24500 KB Output is correct
5 Correct 27 ms 24500 KB Output is correct
6 Correct 26 ms 24500 KB Output is correct
7 Correct 28 ms 24500 KB Output is correct
8 Correct 28 ms 24500 KB Output is correct
9 Correct 89 ms 37292 KB Output is correct
10 Correct 31 ms 25932 KB Output is correct
11 Correct 61 ms 31252 KB Output is correct
12 Correct 31 ms 26384 KB Output is correct
13 Correct 44 ms 29204 KB Output is correct
14 Correct 28 ms 24756 KB Output is correct
15 Correct 28 ms 24756 KB Output is correct
16 Correct 76 ms 37220 KB Output is correct
17 Correct 26 ms 24488 KB Output is correct
18 Correct 26 ms 24500 KB Output is correct
19 Correct 25 ms 24528 KB Output is correct
20 Correct 27 ms 24500 KB Output is correct
21 Correct 27 ms 24500 KB Output is correct
22 Correct 26 ms 24492 KB Output is correct
23 Correct 155 ms 49176 KB Output is correct
24 Correct 26 ms 24492 KB Output is correct
25 Correct 28 ms 24748 KB Output is correct
26 Correct 28 ms 25012 KB Output is correct
27 Correct 28 ms 25004 KB Output is correct
28 Correct 76 ms 34472 KB Output is correct
29 Correct 121 ms 38720 KB Output is correct
30 Correct 115 ms 44188 KB Output is correct
31 Correct 148 ms 49940 KB Output is correct
32 Correct 26 ms 24688 KB Output is correct
33 Correct 26 ms 24500 KB Output is correct
34 Correct 27 ms 24492 KB Output is correct
35 Correct 34 ms 24492 KB Output is correct
36 Correct 26 ms 24500 KB Output is correct
37 Correct 25 ms 24488 KB Output is correct
38 Correct 25 ms 24492 KB Output is correct
39 Correct 27 ms 24488 KB Output is correct
40 Correct 26 ms 24492 KB Output is correct
41 Correct 28 ms 24492 KB Output is correct
42 Correct 27 ms 24492 KB Output is correct
43 Correct 34 ms 24848 KB Output is correct
44 Correct 28 ms 25000 KB Output is correct
45 Correct 81 ms 36132 KB Output is correct
46 Correct 112 ms 42268 KB Output is correct
47 Correct 108 ms 42268 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24492 KB Output is correct
2 Correct 26 ms 24500 KB Output is correct
3 Correct 25 ms 24492 KB Output is correct
4 Correct 26 ms 24500 KB Output is correct
5 Correct 27 ms 24500 KB Output is correct
6 Correct 26 ms 24500 KB Output is correct
7 Correct 28 ms 24500 KB Output is correct
8 Correct 28 ms 24500 KB Output is correct
9 Correct 89 ms 37292 KB Output is correct
10 Correct 31 ms 25932 KB Output is correct
11 Correct 61 ms 31252 KB Output is correct
12 Correct 31 ms 26384 KB Output is correct
13 Correct 44 ms 29204 KB Output is correct
14 Correct 28 ms 24756 KB Output is correct
15 Correct 28 ms 24756 KB Output is correct
16 Correct 76 ms 37220 KB Output is correct
17 Correct 26 ms 24488 KB Output is correct
18 Correct 26 ms 24500 KB Output is correct
19 Correct 25 ms 24528 KB Output is correct
20 Correct 27 ms 24500 KB Output is correct
21 Correct 27 ms 24500 KB Output is correct
22 Correct 26 ms 24492 KB Output is correct
23 Correct 155 ms 49176 KB Output is correct
24 Correct 26 ms 24492 KB Output is correct
25 Correct 28 ms 24748 KB Output is correct
26 Correct 28 ms 25012 KB Output is correct
27 Correct 28 ms 25004 KB Output is correct
28 Correct 76 ms 34472 KB Output is correct
29 Correct 121 ms 38720 KB Output is correct
30 Correct 115 ms 44188 KB Output is correct
31 Correct 148 ms 49940 KB Output is correct
32 Correct 26 ms 24688 KB Output is correct
33 Correct 26 ms 24500 KB Output is correct
34 Correct 27 ms 24492 KB Output is correct
35 Correct 34 ms 24492 KB Output is correct
36 Correct 26 ms 24500 KB Output is correct
37 Correct 25 ms 24488 KB Output is correct
38 Correct 25 ms 24492 KB Output is correct
39 Correct 27 ms 24488 KB Output is correct
40 Correct 26 ms 24492 KB Output is correct
41 Correct 28 ms 24492 KB Output is correct
42 Correct 27 ms 24492 KB Output is correct
43 Correct 34 ms 24848 KB Output is correct
44 Correct 28 ms 25000 KB Output is correct
45 Correct 81 ms 36132 KB Output is correct
46 Correct 112 ms 42268 KB Output is correct
47 Correct 108 ms 42268 KB Output is correct
48 Incorrect 27 ms 24504 KB Tree @(5, 3) appears more than once: for edges on positions 1 and 2
49 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24492 KB Output is correct
2 Correct 26 ms 24500 KB Output is correct
3 Correct 25 ms 24492 KB Output is correct
4 Correct 26 ms 24500 KB Output is correct
5 Correct 27 ms 24500 KB Output is correct
6 Correct 26 ms 24500 KB Output is correct
7 Correct 28 ms 24500 KB Output is correct
8 Correct 28 ms 24500 KB Output is correct
9 Correct 89 ms 37292 KB Output is correct
10 Correct 31 ms 25932 KB Output is correct
11 Correct 61 ms 31252 KB Output is correct
12 Correct 31 ms 26384 KB Output is correct
13 Correct 44 ms 29204 KB Output is correct
14 Correct 28 ms 24756 KB Output is correct
15 Correct 28 ms 24756 KB Output is correct
16 Correct 76 ms 37220 KB Output is correct
17 Correct 26 ms 24496 KB Output is correct
18 Correct 26 ms 24748 KB Output is correct
19 Correct 26 ms 24500 KB Output is correct
20 Correct 217 ms 49064 KB Output is correct
21 Incorrect 170 ms 49096 KB Tree @(11, 5) appears more than once: for edges on positions 7 and 10
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24492 KB Output is correct
2 Correct 26 ms 24500 KB Output is correct
3 Correct 25 ms 24492 KB Output is correct
4 Correct 26 ms 24500 KB Output is correct
5 Correct 27 ms 24500 KB Output is correct
6 Correct 26 ms 24500 KB Output is correct
7 Correct 28 ms 24500 KB Output is correct
8 Correct 28 ms 24500 KB Output is correct
9 Correct 89 ms 37292 KB Output is correct
10 Correct 31 ms 25932 KB Output is correct
11 Correct 61 ms 31252 KB Output is correct
12 Correct 31 ms 26384 KB Output is correct
13 Correct 44 ms 29204 KB Output is correct
14 Correct 28 ms 24756 KB Output is correct
15 Correct 28 ms 24756 KB Output is correct
16 Correct 76 ms 37220 KB Output is correct
17 Correct 157 ms 48004 KB Output is correct
18 Incorrect 155 ms 47896 KB Tree @(50003, 50001) appears more than once: for edges on positions 74999 and 124999
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24492 KB Output is correct
2 Correct 26 ms 24500 KB Output is correct
3 Correct 25 ms 24492 KB Output is correct
4 Correct 26 ms 24500 KB Output is correct
5 Correct 27 ms 24500 KB Output is correct
6 Correct 26 ms 24500 KB Output is correct
7 Correct 28 ms 24500 KB Output is correct
8 Correct 28 ms 24500 KB Output is correct
9 Correct 89 ms 37292 KB Output is correct
10 Correct 31 ms 25932 KB Output is correct
11 Correct 61 ms 31252 KB Output is correct
12 Correct 31 ms 26384 KB Output is correct
13 Correct 44 ms 29204 KB Output is correct
14 Correct 28 ms 24756 KB Output is correct
15 Correct 28 ms 24756 KB Output is correct
16 Correct 76 ms 37220 KB Output is correct
17 Correct 26 ms 24488 KB Output is correct
18 Correct 26 ms 24500 KB Output is correct
19 Correct 25 ms 24528 KB Output is correct
20 Correct 27 ms 24500 KB Output is correct
21 Correct 27 ms 24500 KB Output is correct
22 Correct 26 ms 24492 KB Output is correct
23 Correct 155 ms 49176 KB Output is correct
24 Correct 26 ms 24492 KB Output is correct
25 Correct 28 ms 24748 KB Output is correct
26 Correct 28 ms 25012 KB Output is correct
27 Correct 28 ms 25004 KB Output is correct
28 Correct 76 ms 34472 KB Output is correct
29 Correct 121 ms 38720 KB Output is correct
30 Correct 115 ms 44188 KB Output is correct
31 Correct 148 ms 49940 KB Output is correct
32 Correct 26 ms 24688 KB Output is correct
33 Correct 26 ms 24500 KB Output is correct
34 Correct 27 ms 24492 KB Output is correct
35 Correct 34 ms 24492 KB Output is correct
36 Correct 26 ms 24500 KB Output is correct
37 Correct 25 ms 24488 KB Output is correct
38 Correct 25 ms 24492 KB Output is correct
39 Correct 27 ms 24488 KB Output is correct
40 Correct 26 ms 24492 KB Output is correct
41 Correct 28 ms 24492 KB Output is correct
42 Correct 27 ms 24492 KB Output is correct
43 Correct 34 ms 24848 KB Output is correct
44 Correct 28 ms 25000 KB Output is correct
45 Correct 81 ms 36132 KB Output is correct
46 Correct 112 ms 42268 KB Output is correct
47 Correct 108 ms 42268 KB Output is correct
48 Incorrect 27 ms 24504 KB Tree @(5, 3) appears more than once: for edges on positions 1 and 2
49 Halted 0 ms 0 KB -