oj.uz

Submission #666349

# Submission time Handle Problem Language Result Execution time Memory
666349 2022-11-28T08:55:24 Z mychecksedad Stranded Far From Home (BOI22_island) C++17
10 / 100
 211 ms 33588 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(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]){
                if(ans[u] == -1) continue;
                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 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 7 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 6 ms 9736 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 142 ms 27620 KB Output is correct
4 Correct 158 ms 31284 KB Output is correct
5 Correct 187 ms 27928 KB Output is correct
6 Correct 200 ms 28388 KB Output is correct
7 Correct 171 ms 28480 KB Output is correct
8 Correct 209 ms 31436 KB Output is correct
9 Correct 145 ms 27884 KB Output is correct
10 Correct 95 ms 25776 KB Output is correct
11 Correct 140 ms 33588 KB Output is correct
12 Correct 173 ms 31212 KB Output is correct
13 Correct 132 ms 31168 KB Output is correct
14 Correct 145 ms 31228 KB Output is correct
15 Correct 144 ms 31180 KB Output is correct
16 Correct 103 ms 31004 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9732 KB Output is correct
2 Incorrect 211 ms 28404 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 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 7 ms 9812 KB Output isn't correct
5 Halted 0 ms 0 KB -