oj.uz

Submission #441799

# Submission time Handle Problem Language Result Execution time Memory
441799 2021-07-06T08:08:57 Z baluteshih Fountain Parks (IOI21_parks) C++17
5 / 100
 149 ms 15820 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define SZ(a) ((int)a.size())

int construct_roads(vector<int> x, vector<int> y) {
    if (x.size() == 1) {
	    build({}, {}, {}, {});
        return 1;
    }
    int n = SZ(x);
    vector<int> idx(n);
    iota(ALL(idx), 0);
    sort(ALL(idx), [&](int p, int q){ return y[p] < y[q]; });
    vector<int> u, v, a, b;
    for (int i = 0; i + 1 < n; ++i) {
        if (y[idx[i + 1]] - y[idx[i]] > 2)
            return 0;
        u.pb(idx[i]);
        v.pb(idx[i + 1]);
        a.pb(x[idx[i]] + 1);
        b.pb(y[idx[i]] + 1);
    }
    build(u, v, a, b);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 68 ms 7852 KB Output is correct
10 Correct 6 ms 1228 KB Output is correct
11 Correct 37 ms 4352 KB Output is correct
12 Correct 9 ms 1668 KB Output is correct
13 Correct 10 ms 2168 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 69 ms 7904 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 68 ms 7852 KB Output is correct
10 Correct 6 ms 1228 KB Output is correct
11 Correct 37 ms 4352 KB Output is correct
12 Correct 9 ms 1668 KB Output is correct
13 Correct 10 ms 2168 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 69 ms 7904 KB Output is correct
17 Incorrect 1 ms 208 KB Tree (a[0], b[0]) = (5, 3) is not adjacent to edge between u[0]=2 @(4, 2) and v[0]=3 @(2, 2)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 68 ms 7852 KB Output is correct
10 Correct 6 ms 1228 KB Output is correct
11 Correct 37 ms 4352 KB Output is correct
12 Correct 9 ms 1668 KB Output is correct
13 Correct 10 ms 2168 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 69 ms 7904 KB Output is correct
17 Incorrect 1 ms 208 KB Tree (a[0], b[0]) = (5, 3) is not adjacent to edge between u[0]=2 @(4, 2) and v[0]=3 @(2, 2)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 68 ms 7852 KB Output is correct
10 Correct 6 ms 1228 KB Output is correct
11 Correct 37 ms 4352 KB Output is correct
12 Correct 9 ms 1668 KB Output is correct
13 Correct 10 ms 2168 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 69 ms 7904 KB Output is correct
17 Incorrect 0 ms 204 KB Tree (a[0], b[0]) = (200001, 3) is not adjacent to edge between u[0]=0 @(200000, 2) and v[0]=2 @(199998, 2)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 68 ms 7852 KB Output is correct
10 Correct 6 ms 1228 KB Output is correct
11 Correct 37 ms 4352 KB Output is correct
12 Correct 9 ms 1668 KB Output is correct
13 Correct 10 ms 2168 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 69 ms 7904 KB Output is correct
17 Incorrect 149 ms 15820 KB Pair u[0]=144319 @(81514, 2) and v[0]=55086 @(31010, 2) does not form a valid edge (distance != 2)
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 68 ms 7852 KB Output is correct
10 Correct 6 ms 1228 KB Output is correct
11 Correct 37 ms 4352 KB Output is correct
12 Correct 9 ms 1668 KB Output is correct
13 Correct 10 ms 2168 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 69 ms 7904 KB Output is correct
17 Incorrect 1 ms 208 KB Tree (a[0], b[0]) = (5, 3) is not adjacent to edge between u[0]=2 @(4, 2) and v[0]=3 @(2, 2)
18 Halted 0 ms 0 KB -