Submission #730355

#	Time	Username	Problem	Language	Result	Execution time	Memory
730355		_martynas	Stranded Far From Home (BOI22_island)	C++11	100 / 100	299 ms	33604 KiB

island

//https://oj.uz/submission/694082
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using pli = pair<ll, int>;
using vi = vector<int>;
using vl = vector<ll>;
 
#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
 
const int MXN = 2e5+5;
 
int n, m;
ll A[MXN];
vi adj[MXN];
vi res_adj[MXN]; // directional graph describes how I propagate results
 
struct DSU {
    int n;
    vi par;
    vi sz;
    vi mx_id;
    vl pop;
    void init(int _n) {
        n = _n;
        par = vi(n+1);
        sz = vi(n+1, 1);
        mx_id = vi(n+1);
        pop = vl(n+1);
        iota(par.begin()+1, par.begin()+n+1, 1);
        iota(mx_id.begin()+1, mx_id.begin()+n+1, 1);
        for(int i = 1; i <= n; i++) pop[i] = A[i];
    }
    int find_set(int u) { return par[u] == u ? u : par[u] = find_set(par[u]); }
    void unite(int u, int v) {
        u = find_set(u), v = find_set(v);
        if(u == v) return;
        int new_mx_id = A[mx_id[u]] >= A[mx_id[v]] ? mx_id[u] : mx_id[v];
        if(sz[u] < sz[v]) swap(u, v);
        mx_id[u] = new_mx_id;
        par[v] = u;
        sz[u] += sz[v];
        pop[u] += pop[v];
    }
};
 
int main() {
  	ios::sync_with_stdio(0);
  	cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> A[i];
    for(int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].PB(v), adj[v].PB(u);
    }
    string ans(n+1, '0');
    ll mx = *max_element(A+1, A+n+1);
    vector<pli> B;
    for(int i = 1; i <= n; i++) {
        if(A[i] == mx) ans[i] = '1';
        B.PB({A[i], i});
    }
    sort(all(B));
    DSU dsu;
    dsu.init(n);
    for(auto p : B) {
        int u = p.S;
        for(int v : adj[u]) {
            if(A[v] <= A[u]) {
                if(dsu.pop[dsu.find_set(v)] >= A[u]) {
                    res_adj[u].PB(dsu.mx_id[dsu.find_set(v)]);
                }
            }
        }
        for(int v : adj[u]) {
            if(A[v] <= A[u]) {
                dsu.unite(u, v);
            }
        }
    }
    queue<int> Q;
    for(int i = 1; i <= n; i++) if(ans[i] == '1') Q.push(i);
    while(!Q.empty()) {
        int i = Q.front();
        Q.pop();
        for(int j : res_adj[i]) {
            if(ans[j] == '0') {
                ans[j] = '1';
                Q.push(j);
            }
        }
    }
    cout << ans.substr(1) << "\n";
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35