oj.uz

Submission #666331

# Submission time Handle Problem Language Result Execution time Memory
666331 2022-11-28T08:21:27 Z mychecksedad Stranded Far From Home (BOI22_island) C++17
10 / 100
 218 ms 33680 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;
    for(int i = 1; i <= n; ++i) if(a[i] == b[n].first) q.push(i), vis[i] = 1;
    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 9720 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 145 ms 26024 KB Output is correct
4 Correct 155 ms 31164 KB Output is correct
5 Correct 170 ms 28860 KB Output is correct
6 Correct 183 ms 29416 KB Output is correct
7 Correct 172 ms 29616 KB Output is correct
8 Correct 201 ms 32432 KB Output is correct
9 Correct 141 ms 28908 KB Output is correct
10 Correct 109 ms 26048 KB Output is correct
11 Correct 137 ms 33680 KB Output is correct
12 Correct 175 ms 30924 KB Output is correct
13 Correct 148 ms 30792 KB Output is correct
14 Correct 149 ms 31148 KB Output is correct
15 Correct 163 ms 32364 KB Output is correct
16 Correct 97 ms 31532 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9612 KB Output is correct
2 Incorrect 182 ms 26744 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 218 ms 26420 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 9720 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 -