oj.uz

Submission #1025297

# Submission time Handle Problem Language Result Execution time Memory
1025297 2024-07-16T19:26:14 Z overwatch9 Stranded Far From Home (BOI22_island) C++17
0 / 100
 1000 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 1;
ll S[maxn];
vector <int> adj[maxn];
vector <int> mark[maxn];
bool ans[maxn];
bool inserted[maxn], vis[maxn], in_marked[maxn];
int id[maxn];
struct DSU {
    vector <int> link, sz, lst_added;
    vector <ll> sum;
    DSU (int s) {
        lst_added = link = sz = vector <int> (s+1);
        sum = vector <ll> (s+1);
        for (int i = 1; i <= s; i++) {
            lst_added[i] = link[i] = i;
            sz[i] = 1;
            sum[i] = S[i];
        }
    }
    int head(int x) {
        while (x != link[x])
            x = link[x];
        return x;
    }
    bool same(int a, int b) {
        return head(a) == head(b);
    }
    void unite(int a, int b) {
        a = head(a);
        b = head(b);
        if (a == b)
            return;
        if (sz[a] > sz[b])
            swap(a, b);
        sz[a] += sz[b];
        sum[a] += sum[b];
        link[b] = a;
        if (id[lst_added[a]] > id[lst_added[b]])
            lst_added[a] = lst_added[a];
        else
            lst_added[a] = lst_added[b];
    }
};
void dfs(int s, bool x) {
    ans[s] &= x;
    for (auto i : mark[s])
        dfs(i, ans[s]);
}
int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    int n, m;
    cin >> n >> m;
    fill(ans, ans + n + 1, true);
    for (int i = 1; i <= n; i++)
        cin >> S[i];
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    DSU dsu(n+1);
    vector <pair <int, int>> nodes;
    for (int i = 1; i <= n; i++) {
        nodes.push_back({S[i], i});
    }
    sort(nodes.begin(), nodes.end());
    for (int i = 0; i < n; i++)
        id[nodes[i].second] = i;
    for (int i = 0; i < n; i++) {
        for (auto j : adj[nodes[i].second]) {
            if (!vis[j])
                continue;
            int x = dsu.lst_added[dsu.head(j)];
            if (dsu.sum[dsu.head(j)] < nodes[i].first)
                ans[x] = false;
            if (!in_marked[x] && i != x) {
                in_marked[x] = true;
                mark[nodes[i].second].push_back(x);
            }
            dsu.unite(nodes[i].second, j);
        }
        vis[nodes[i].second] = true;
    }
    dfs(nodes[n-1].second, true);
    for (int i = 1; i <= n; i++)
        cout << ans[i];
    cout << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Runtime error 476 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 160 ms 31264 KB Output is correct
4 Correct 155 ms 35784 KB Output is correct
5 Correct 173 ms 28356 KB Output is correct
6 Correct 158 ms 28876 KB Output is correct
7 Correct 189 ms 28872 KB Output is correct
8 Execution timed out 1073 ms 26060 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Incorrect 190 ms 28984 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Execution timed out 1098 ms 28480 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Runtime error 476 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -