oj.uz

Submission #593668

# Submission time Handle Problem Language Result Execution time Memory
593668 2022-07-11T13:29:18 Z SlavicG Fountain Parks (IOI21_parks) C++17
5 / 100
 204 ms 20932 KB 
#include "parks.h"
#include "bits/stdc++.h"
using namespace std;

#define     sz(a)     (int)a.size()
#define    all(a)     a.begin(),a.end()



int construct_roads(vector<int> x, vector<int> y) {
    if (x.size() == 1) {
        build({}, {}, {}, {});
        return 1;
    }
    vector<int> u, v, a, b;
    vector<pair<int, int>> points;
    map<pair<int, int>, int> idx;
    for(int i = 0; i < sz(x); ++i) {
        idx[{x[i], y[i]}] = i;
        points.push_back({x[i], y[i]});
    }
    sort(all(points));
    for(int i = 0; i + 1 < sz(points); ++i) {
        if(points[i].second + 2 < points[i + 1].second) return 0;
        u.push_back(idx[points[i]]), v.push_back(idx[points[i + 1]]);
        a.push_back(points[i].first - 1);
        b.push_back(points[i].second + 1);
    }
    build(u, v, a, b);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 122 ms 15148 KB Output is correct
10 Correct 9 ms 1796 KB Output is correct
11 Correct 54 ms 8164 KB Output is correct
12 Correct 15 ms 2492 KB Output is correct
13 Correct 25 ms 5196 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 133 ms 15208 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 122 ms 15148 KB Output is correct
10 Correct 9 ms 1796 KB Output is correct
11 Correct 54 ms 8164 KB Output is correct
12 Correct 15 ms 2492 KB Output is correct
13 Correct 25 ms 5196 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 133 ms 15208 KB Output is correct
17 Incorrect 1 ms 296 KB Pair u[1]=1 @(2, 4) and v[1]=2 @(4, 2) does not form a valid edge (distance != 2)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 122 ms 15148 KB Output is correct
10 Correct 9 ms 1796 KB Output is correct
11 Correct 54 ms 8164 KB Output is correct
12 Correct 15 ms 2492 KB Output is correct
13 Correct 25 ms 5196 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 133 ms 15208 KB Output is correct
17 Incorrect 1 ms 296 KB Pair u[1]=1 @(2, 4) and v[1]=2 @(4, 2) does not form a valid edge (distance != 2)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 122 ms 15148 KB Output is correct
10 Correct 9 ms 1796 KB Output is correct
11 Correct 54 ms 8164 KB Output is correct
12 Correct 15 ms 2492 KB Output is correct
13 Correct 25 ms 5196 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 133 ms 15208 KB Output is correct
17 Incorrect 1 ms 212 KB Tree (a[0], b[0]) = (199997, 3) is not adjacent to edge between u[0]=2 @(199998, 2) and v[0]=0 @(200000, 2)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 122 ms 15148 KB Output is correct
10 Correct 9 ms 1796 KB Output is correct
11 Correct 54 ms 8164 KB Output is correct
12 Correct 15 ms 2492 KB Output is correct
13 Correct 25 ms 5196 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 133 ms 15208 KB Output is correct
17 Incorrect 204 ms 20932 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 122 ms 15148 KB Output is correct
10 Correct 9 ms 1796 KB Output is correct
11 Correct 54 ms 8164 KB Output is correct
12 Correct 15 ms 2492 KB Output is correct
13 Correct 25 ms 5196 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 133 ms 15208 KB Output is correct
17 Incorrect 1 ms 296 KB Pair u[1]=1 @(2, 4) and v[1]=2 @(4, 2) does not form a valid edge (distance != 2)
18 Halted 0 ms 0 KB -