oj.uz

Submission #666356

# Submission time Handle Problem Language Result Execution time Memory
666356 2022-11-28T09:10:40 Z mychecksedad Stranded Far From Home (BOI22_island) C++17
10 / 100
 199 ms 23200 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;


int a[N];
struct Dsu{
    vector<int> s, p, mx;
    vector<long long> sum;
    Dsu(int n){
        s.resize(n + 1, 1);
        p.resize(n + 1);
        mx.resize(n + 1);
        sum.resize(n + 1, 0ll);
        for(int i = 0; i <= n; ++i) p[i] = mx[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 c, int b){
        c = find(c);
        b = find(b);
        if(c != b){
            if(s[c] > s[b]) swap(c, b);
            p[c] = b;
            s[b] += s[c];
            sum[b] += sum[c];
            mx[b] = a[mx[c]] > a[mx[b]] ? mx[c] : mx[b];
        }
    }
};


int n, m;
vector<int> g[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), M(n);
    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.merge(v, d.mx[co]);
                }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);

    int co = M.find(b[n].second);

    for(int i = 1; i <= n; ++i) ans[i] = (M.find(i) == co ? 1 : 0);


    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 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 4 ms 5076 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 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 136 ms 22432 KB Output is correct
4 Correct 124 ms 22400 KB Output is correct
5 Correct 147 ms 21916 KB Output is correct
6 Correct 151 ms 22484 KB Output is correct
7 Correct 149 ms 22468 KB Output is correct
8 Correct 138 ms 22548 KB Output is correct
9 Correct 128 ms 22476 KB Output is correct
10 Correct 99 ms 23156 KB Output is correct
11 Correct 118 ms 23200 KB Output is correct
12 Correct 150 ms 22556 KB Output is correct
13 Correct 123 ms 22480 KB Output is correct
14 Correct 121 ms 22420 KB Output is correct
15 Correct 133 ms 22476 KB Output is correct
16 Correct 85 ms 22304 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 172 ms 22348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 199 ms 22392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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