oj.uz

Submission #640387

# Submission time Handle Problem Language Result Execution time Memory
640387 2022-09-14T14:00:46 Z christinelynn Stranded Far From Home (BOI22_island) C++17
0 / 100
 237 ms 30776 KB 
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<numeric>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<set>
using namespace std;

#define ll long long
#define ld long double

struct DSU{
    vector<vector<int>> group;
    vector<int> par;
    vector<ll> sz, val;
    int N;

    DSU(int _N){
        N = _N;
        sz = vector<ll>(N+1);
        val = vector<ll>(N+1);
        par = vector<int>(N+1); iota(par.begin(), par.end(), 0);
        group = vector<vector<int>>(N+1); for(int i = 1; i <= N; ++i)group[i].push_back(i);
    }

    int rep(int x){
        if(par[x] == x)return x;
        return par[x] = rep(par[x]);
    }

    void comb(int u, int v){
        int pu = rep(u), pv = rep(v);
        if(pu != pv){
            if(val[pv] < sz[u]){
                vector<int>().swap(group[v]);
            }
            if((int)group[pu].size() > (int)group[pv].size()){
                swap(pu, pv);
            }
            for(int elem : group[pu]){
                group[pv].push_back(elem);
            }
            vector<int>().swap(group[pu]);
            val[pv] += val[pu];
            par[pu] = pv;
        }
    }
};

vector<int> adj[200005];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N, M; cin >> N >> M;

    DSU dsu(N);

    vector<pair<int, int>> order;
    for(int i = 1; i <= N; ++i){
        int x; cin >> x;
        dsu.val[i] = dsu.sz[i] = x;
        order.push_back({x, i});
    }

    for(int i = 1; i <= M; ++i){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    sort(order.begin(), order.end());

    vector<bool> vis(N+1);
    for(int i = 0; i < N; ++i){
        int cur = order[i].second;
        vis[cur] = 1;
        for(int nx : adj[cur]){
            if(vis[nx]){
                dsu.comb(cur, nx);
            }
        }
    }

    vector<bool> answer(N+1);
    for(int elem : dsu.group[dsu.rep(1)]){
        answer[elem] = 1;
    }

    for(int i = 1; i <= N; ++i){
        cout << answer[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 4932 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 4 ms 5236 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 149 ms 29684 KB Output is correct
4 Correct 141 ms 30340 KB Output is correct
5 Incorrect 185 ms 30144 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 215 ms 30180 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 5024 KB Output is correct
2 Incorrect 237 ms 30776 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 4932 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 4 ms 5236 KB Output isn't correct
5 Halted 0 ms 0 KB -