oj.uz

Submission #1025301

# Submission time Handle Problem Language Result Execution time Memory
1025301 2024-07-16T19:33:34 Z overwatch9 Stranded Far From Home (BOI22_island) C++17
25 / 100
 1000 ms 36292 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] && nodes[i].second != 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 3 ms 12756 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 5 ms 12788 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 5 ms 12892 KB Output is correct
7 Correct 4 ms 12764 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 9 ms 12944 KB Output is correct
10 Correct 3 ms 12888 KB Output is correct
11 Correct 3 ms 12888 KB Output is correct
12 Correct 4 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct

Subtask #2
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 169 ms 31292 KB Output is correct
4 Correct 143 ms 35680 KB Output is correct
5 Correct 146 ms 28352 KB Output is correct
6 Correct 182 ms 28988 KB Output is correct
7 Correct 152 ms 28740 KB Output is correct
8 Execution timed out 1012 ms 26056 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 177 ms 28984 KB Output is correct
3 Correct 195 ms 28864 KB Output is correct
4 Correct 173 ms 36288 KB Output is correct
5 Correct 135 ms 34624 KB Output is correct
6 Correct 196 ms 28868 KB Output is correct
7 Correct 163 ms 36152 KB Output is correct
8 Correct 174 ms 36292 KB Output is correct
9 Correct 130 ms 35880 KB Output is correct
10 Correct 157 ms 30404 KB Output is correct
11 Correct 155 ms 29892 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Execution timed out 1093 ms 28604 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 3 ms 12756 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 5 ms 12788 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 5 ms 12892 KB Output is correct
7 Correct 4 ms 12764 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 9 ms 12944 KB Output is correct
10 Correct 3 ms 12888 KB Output is correct
11 Correct 3 ms 12888 KB Output is correct
12 Correct 4 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 2 ms 12636 KB Output is correct
16 Correct 2 ms 12636 KB Output is correct
17 Correct 169 ms 31292 KB Output is correct
18 Correct 143 ms 35680 KB Output is correct
19 Correct 146 ms 28352 KB Output is correct
20 Correct 182 ms 28988 KB Output is correct
21 Correct 152 ms 28740 KB Output is correct
22 Execution timed out 1012 ms 26056 KB Time limit exceeded
23 Halted 0 ms 0 KB -