oj.uz

Submission #666339

# Submission time Handle Problem Language Result Execution time Memory
666339 2022-11-28T08:33:30 Z mychecksedad Stranded Far From Home (BOI22_island) C++17
10 / 100
 215 ms 30336 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 5 ms 9632 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 7 ms 9752 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 153 ms 26008 KB Output is correct
4 Correct 170 ms 28108 KB Output is correct
5 Correct 177 ms 24792 KB Output is correct
6 Correct 173 ms 25068 KB Output is correct
7 Correct 185 ms 25140 KB Output is correct
8 Correct 207 ms 27984 KB Output is correct
9 Correct 167 ms 24540 KB Output is correct
10 Correct 112 ms 22440 KB Output is correct
11 Correct 131 ms 30336 KB Output is correct
12 Correct 190 ms 27804 KB Output is correct
13 Correct 152 ms 27948 KB Output is correct
14 Correct 162 ms 27904 KB Output is correct
15 Correct 146 ms 27908 KB Output is correct
16 Correct 113 ms 27760 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Incorrect 215 ms 26268 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 9632 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 7 ms 9752 KB Output isn't correct
5 Halted 0 ms 0 KB -