oj.uz

Submission #593783

# Submission time Handle Problem Language Result Execution time Memory
593783 2022-07-11T15:17:47 Z SlavicG Fountain Parks (IOI21_parks) C++17
5 / 100
 237 ms 53264 KB 
#include "parks.h"
#include "bits/stdc++.h"
using namespace std;

#define         sz(a)     (int)a.size()
#define        all(a)     a.begin(),a.end()
#define    forn(i, n)     for(int i = 0; i < n; ++i)

const int N = 2e5 + 10;
int p[N];
int get(int a) {
    return p[a] = (a == p[a] ? a : get(p[a]));
}
bool uni(int a, int b) {
    a = get(a), b = get(b);
    if(a == b) return false;
    p[a] = b;
    return true;
}

int construct_roads(vector<int> x, vector<int> y) {
    forn(i, N) p[i] = i;
    if (x.size() == 1) {
        build({}, {}, {}, {});
        return 1;
    }
    vector<int> u, v, a, b;
    vector<pair<int, int>> points;
    map<pair<int, int>, int> idx;
    vector<int> bruh[N];
    for(int i = 0; i < sz(x); ++i) {
        bruh[y[i]].push_back(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].first == points[i + 1].first) {
            if(points[i].second + 2 != points[i + 1].second) continue;
            if(points[i].first == 2 && uni(idx[points[i]], idx[points[i + 1]])) {
                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);
            } else if(points[i].first == 4 && uni(idx[points[i]], idx[points[i + 1]])) {
                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);
            }
        }
    }
    for(auto v: bruh) {
        if(sz(v) >= 2) {
            assert(sz(v) == 2);
            if(uni(v[0], v[1])) {
                u.push_back(v[0]);
                u.push_back(v[1]);
                a.push_back(3);
                b.push_back(y[v[0]] - 1);
            }
        }
    }
    for(int i = 1; i < sz(x); ++i) {
        if(get(i) != get(0)) return 0;
    }
    build(u, v, a, b);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5716 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 4 ms 5776 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 4 ms 5716 KB Output is correct
9 Correct 193 ms 24084 KB Output is correct
10 Correct 15 ms 7684 KB Output is correct
11 Correct 63 ms 15620 KB Output is correct
12 Correct 19 ms 8540 KB Output is correct
13 Correct 39 ms 12612 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 6 ms 6064 KB Output is correct
16 Correct 170 ms 23708 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5716 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 4 ms 5776 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 4 ms 5716 KB Output is correct
9 Correct 193 ms 24084 KB Output is correct
10 Correct 15 ms 7684 KB Output is correct
11 Correct 63 ms 15620 KB Output is correct
12 Correct 19 ms 8540 KB Output is correct
13 Correct 39 ms 12612 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 6 ms 6064 KB Output is correct
16 Correct 170 ms 23708 KB Output is correct
17 Incorrect 3 ms 5716 KB Wrong answer detected in grader
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5716 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 4 ms 5776 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 4 ms 5716 KB Output is correct
9 Correct 193 ms 24084 KB Output is correct
10 Correct 15 ms 7684 KB Output is correct
11 Correct 63 ms 15620 KB Output is correct
12 Correct 19 ms 8540 KB Output is correct
13 Correct 39 ms 12612 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 6 ms 6064 KB Output is correct
16 Correct 170 ms 23708 KB Output is correct
17 Incorrect 3 ms 5716 KB Wrong answer detected in grader
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5716 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 4 ms 5776 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 4 ms 5716 KB Output is correct
9 Correct 193 ms 24084 KB Output is correct
10 Correct 15 ms 7684 KB Output is correct
11 Correct 63 ms 15620 KB Output is correct
12 Correct 19 ms 8540 KB Output is correct
13 Correct 39 ms 12612 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 6 ms 6064 KB Output is correct
16 Correct 170 ms 23708 KB Output is correct
17 Incorrect 4 ms 5716 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5716 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 4 ms 5776 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 4 ms 5716 KB Output is correct
9 Correct 193 ms 24084 KB Output is correct
10 Correct 15 ms 7684 KB Output is correct
11 Correct 63 ms 15620 KB Output is correct
12 Correct 19 ms 8540 KB Output is correct
13 Correct 39 ms 12612 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 6 ms 6064 KB Output is correct
16 Correct 170 ms 23708 KB Output is correct
17 Runtime error 237 ms 53264 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5716 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 4 ms 5776 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 4 ms 5716 KB Output is correct
9 Correct 193 ms 24084 KB Output is correct
10 Correct 15 ms 7684 KB Output is correct
11 Correct 63 ms 15620 KB Output is correct
12 Correct 19 ms 8540 KB Output is correct
13 Correct 39 ms 12612 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 6 ms 6064 KB Output is correct
16 Correct 170 ms 23708 KB Output is correct
17 Incorrect 3 ms 5716 KB Wrong answer detected in grader
18 Halted 0 ms 0 KB -