oj.uz

Submission #593781

# Submission time Handle Problem Language Result Execution time Memory
593781 2022-07-11T15:15:53 Z SlavicG Fountain Parks (IOI21_parks) C++17
0 / 100
 3 ms 4948 KB 
#include "parks.h"
#include "bits/stdc++.h"
using namespace std;

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

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) {
    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) {
            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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Given structure is not connected: There is no path between vertices 0 and 1
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Given structure is not connected: There is no path between vertices 0 and 1
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Given structure is not connected: There is no path between vertices 0 and 1
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Given structure is not connected: There is no path between vertices 0 and 1
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Given structure is not connected: There is no path between vertices 0 and 1
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Given structure is not connected: There is no path between vertices 0 and 1
3 Halted 0 ms 0 KB -