oj.uz

Submission #666340

# Submission time Handle Problem Language Result Execution time Memory
666340 2022-11-28T08:37:03 Z mychecksedad Stranded Far From Home (BOI22_island) C++17
10 / 100
 216 ms 30324 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, 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);
                }
            }
        }
        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] = ans[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];

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9608 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Incorrect 7 ms 9872 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 7 ms 9684 KB Output is correct
2 Correct 6 ms 9732 KB Output is correct
3 Correct 156 ms 26080 KB Output is correct
4 Correct 144 ms 27888 KB Output is correct
5 Correct 185 ms 24668 KB Output is correct
6 Correct 166 ms 25060 KB Output is correct
7 Correct 183 ms 25144 KB Output is correct
8 Correct 199 ms 28028 KB Output is correct
9 Correct 134 ms 24596 KB Output is correct
10 Correct 99 ms 22392 KB Output is correct
11 Correct 138 ms 30324 KB Output is correct
12 Correct 167 ms 27756 KB Output is correct
13 Correct 146 ms 27932 KB Output is correct
14 Correct 142 ms 27920 KB Output is correct
15 Correct 142 ms 27892 KB Output is correct
16 Correct 102 ms 27696 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 183 ms 26600 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 216 ms 26208 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 7 ms 9608 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Incorrect 7 ms 9872 KB Output isn't correct
5 Halted 0 ms 0 KB -