oj.uz

Submission #1061449

# Submission time Handle Problem Language Result Execution time Memory
1061449 2024-08-16T09:09:14 Z Ignut Fountain Parks (IOI21_parks) C++17
0 / 100
 1 ms 348 KB 
/* Ignut
started: 16.08.2024
now: 16.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);

struct DSU {
    int cntComp;
    vector<int> p, sz;
    void Init(int n) {
        cntComp = n;
        p.assign(n, 0);
        iota(p.begin(), p.end(), 0);
        sz.assign(n, 1);
    }
    int Get(int v) {
        return p[v] == v ? v : p[v] = Get(p[v]);
    }
    void Unite(int u, int v) {
        u = Get(u), v = Get(v);
        if (u == v) return;
        cntComp --;
        if (sz[u] > sz[v]) swap(u, v);
        p[u] = v;
        sz[v] += sz[u];
    }
};

int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    map<pair<int, int>, int> mp;
    for (int i = 0; i < n; i ++) mp[{x[i], y[i]}] = i + 1;

    DSU dsu; dsu.Init(n);
    vector<int> u, v, a, b;
    auto MakeEdge = [&u, &v, &a, &b, &dsu, &x, &y](int i, int j) -> void {
        u.push_back(i);
        v.push_back(j);
        dsu.Unite(i, j);
        int X;
        if (x[i] == 2 && x[j] == 2) X = 1;
        else if (x[i] == 4 && x[j] == 4) X = 5;
        else X = 3;
        int Y;
        if (y[i] == y[j]) Y = y[i] - 1;
        else Y = (y[i] + y[j]) / 2;
        a.push_back(X);
        b.push_back(Y);
    };
    for (int i = 0; i < n; i ++) {
        if (mp.count({x[i] + 2, y[i]})) {
            MakeEdge(i, mp[{x[i] + 2, y[i]}]);
        }
        if (mp.count({x[i], y[i] + 2})) {
            MakeEdge(i, mp[{x[i], y[i] + 2}]);
        }
    }
    if (dsu.cntComp > 1) return 0;
    build(u, v, a, b);
    return 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -