oj.uz

Submission #666357

# Submission time Handle Problem Language Result Execution time Memory
666357 2022-11-28T09:13:03 Z mychecksedad Stranded Far From Home (BOI22_island) C++17
10 / 100
 209 ms 23988 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], pos[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] = pos[mx[c]] > pos[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) pos[b[i].second] = i;
    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 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 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 5048 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 145 ms 23296 KB Output is correct
4 Correct 136 ms 23248 KB Output is correct
5 Correct 145 ms 22648 KB Output is correct
6 Correct 154 ms 23196 KB Output is correct
7 Correct 168 ms 23212 KB Output is correct
8 Correct 145 ms 23252 KB Output is correct
9 Correct 136 ms 23144 KB Output is correct
10 Correct 105 ms 23980 KB Output is correct
11 Correct 126 ms 23988 KB Output is correct
12 Correct 162 ms 23248 KB Output is correct
13 Correct 123 ms 23240 KB Output is correct
14 Correct 117 ms 23172 KB Output is correct
15 Correct 148 ms 23176 KB Output is correct
16 Correct 87 ms 22972 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4960 KB Output is correct
2 Incorrect 176 ms 23104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Incorrect 209 ms 23164 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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