oj.uz

Submission #599795

# Submission time Handle Problem Language Result Execution time Memory
599795 2022-07-19T23:42:01 Z yanndev Stranded Far From Home (BOI22_island) C++17
10 / 100
 52 ms 18396 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

const int MX_N = 1e5 + 42;

int par[MX_N];
int sum[MX_N];
int guys[MX_N];
bool isOk[MX_N];
vector<int> graph[MX_N];
vector<int> dsuTree[MX_N];

int find(int node) {
    if (par[node] < 0)
        return node;
    return par[node] = find(par[node]);
}

void unite(int u, int v) {
    //cout << "edge " << u + 1 << ' ' << v + 1 << '\n';
    u = find(u);
    v = find(v);
    if (u == v)
        return;
    //cout << " compo is " << u + 1 << '\n';
    if (sum[u] < guys[v]) {
        //cout << "nok\n";
        isOk[u] = false;
    }
    par[v] += par[u];
    par[u] = v;
    sum[v] += sum[u];
    dsuTree[v].push_back(u);
}

void upd(int node, bool fuck) {
    //cout << "ucr is " << node << '\n';
    fuck &= isOk[node];
    for (auto& x: dsuTree[node])
        upd(x, fuck);
    isOk[node] = fuck;
}

signed main() {
    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> nodes {};

    for (int i = 0; i < n; i++) {
        cin >> guys[i];
        nodes.push_back({guys[i], i});
        par[i] = -1;
        sum[i] = guys[i];
        isOk[i] = true;
    }
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    sort(nodes.begin(), nodes.end());
    for (int i = 0; i < n; i++)
        for (auto& x: graph[nodes[i].se])
            if (make_pair(guys[x], x) < nodes[i])
                unite(x, nodes[i].se);
    
    upd(nodes.back().se, true);
    /*for (int i = 0; i < n; i++) {
        for (auto& x: dsuTree[i]) {
            cout << "dsu edge " << i + 1 << " to " << x + 1 << '\n';
        }
    }*/
    for (int i = 0; i < n; i++)
        cout << isOk[i];
    cout << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 4 ms 5148 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct
6 Correct 5 ms 5204 KB Output is correct
7 Correct 5 ms 5208 KB Output is correct
8 Correct 4 ms 5176 KB Output is correct
9 Correct 5 ms 5204 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 5 ms 5204 KB Output is correct
12 Correct 5 ms 5204 KB Output is correct
13 Correct 4 ms 5204 KB Output is correct
14 Correct 4 ms 5204 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Runtime error 51 ms 18396 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 4 ms 5148 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct
6 Correct 5 ms 5204 KB Output is correct
7 Correct 5 ms 5208 KB Output is correct
8 Correct 4 ms 5176 KB Output is correct
9 Correct 5 ms 5204 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 5 ms 5204 KB Output is correct
12 Correct 5 ms 5204 KB Output is correct
13 Correct 4 ms 5204 KB Output is correct
14 Correct 4 ms 5204 KB Output is correct
15 Correct 4 ms 4944 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Runtime error 51 ms 18396 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -