oj.uz

Submission #666351

# Submission time Handle Problem Language Result Execution time Memory
666351 2022-11-28T08:56:35 Z mychecksedad Stranded Far From Home (BOI22_island) C++17
10 / 100
 219 ms 31176 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
const int N = 2e5 + 100;

struct Dsu{
    vector<int> s, p;
    vector<long long> sum;
    Dsu(int n, int a[]){
        s.resize(n + 1, 1);
        p.resize(n + 1);
        sum.resize(n + 1, 0ll);
        for(int i = 0; i <= n; ++i) p[i] = i;
        for(int i = 0; i <= n; ++i) sum[i] = a[i];
    }
    int find(int v){
        if(v==p[v]) return v;
        return (p[v]=find(p[v]));
    }
    void merge(int a, int b){
        a = find(a);
        b = find(b);
        if(a != b){
            if(s[a] > s[b]) swap(a, b);
            p[a] = b;
            s[b] += s[a];
            sum[b] += sum[a];
        }
    }
};


int n, m, a[N];
vector<int> g[N], M[N];
vector<bool> vis;
vector<int> ans;
pair<int, int> b[N];
int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) b[i] = {a[i], i};
    for(int i = 0; i < m; ++i){
        int a, b; cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }


    Dsu d(n, a);
    sort(b + 1, b + 1 + n);
    ans.resize(n + 1, 0);
    vis.resize(n + 1, 0);

    for(int i = 1; i <= n; ++i){
        int v = b[i].second;
        for(int u: g[v]){
            if(vis[u]){
                int co = d.find(u);
                if(ans[u] != -1 && d.sum[co] >= a[v]){
                    M[v].pb(u);
                    M[u].pb(v);
                }else{
                    ans[u] = -1;
                }
            }
        }
        for(int u: g[v]){
            if(vis[u]){
                d.merge(u, v);
            }
        }
        vis[v] = 1;
    }   
    vis.clear();
    vis.resize(n+1, 0);

    queue<int> q;
    vis[b[n].second] = 1;
    q.push(b[n].second);

    while(!q.empty()){
        int v = q.front(); q.pop();
        ans[v] = 1;
        for(int u: M[v]){
            if(!vis[u]){
                vis[u] = 1;
                q.push(u);
            }
        }
    }

    for(int i = 1; i <= n; ++i) cout << (ans[i]==-1?0:ans[i]);

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 6 ms 9812 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 144 ms 26728 KB Output is correct
4 Correct 144 ms 28672 KB Output is correct
5 Correct 161 ms 25332 KB Output is correct
6 Correct 181 ms 25860 KB Output is correct
7 Correct 173 ms 25932 KB Output is correct
8 Correct 219 ms 28780 KB Output is correct
9 Correct 137 ms 25256 KB Output is correct
10 Correct 95 ms 23208 KB Output is correct
11 Correct 132 ms 31176 KB Output is correct
12 Correct 179 ms 28540 KB Output is correct
13 Correct 142 ms 28640 KB Output is correct
14 Correct 134 ms 28652 KB Output is correct
15 Correct 161 ms 28612 KB Output is correct
16 Correct 101 ms 28576 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9624 KB Output is correct
2 Incorrect 200 ms 25088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 200 ms 25440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 6 ms 9812 KB Output isn't correct
5 Halted 0 ms 0 KB -