oj.uz

Submission #694061

# Submission time Handle Problem Language Result Execution time Memory
694061 2023-02-03T17:02:42 Z _martynas Stranded Far From Home (BOI22_island) C++14
10 / 100
 347 ms 36944 KB 
#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;
        if(sz[u] < sz[v]) swap(u, v);
        if(A[mx_id[u]] < A[mx_id[v]]) mx_id[u] = mx_id[v];
        par[v] = u;
        sz[u] += sz[v];
        pop[u] += pop[v];
    }
};

int main() {
    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;
}

/*
4 4
2 2 4 3
1 2
1 3
2 3
3 4
ans: 1110
4 3
4 2 2 1
1 2
3 2
4 1
ans: 1110


*/

Subtask #1
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 5 ms 9684 KB Output is correct
4 Correct 9 ms 9812 KB Output is correct
5 Incorrect 7 ms 9812 KB Output isn't correct
6 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 301 ms 33032 KB Output is correct
4 Correct 253 ms 34552 KB Output is correct
5 Correct 315 ms 31460 KB Output is correct
6 Correct 300 ms 32212 KB Output is correct
7 Correct 298 ms 32244 KB Output is correct
8 Correct 330 ms 35904 KB Output is correct
9 Correct 269 ms 30960 KB Output is correct
10 Correct 218 ms 29464 KB Output is correct
11 Correct 253 ms 36944 KB Output is correct
12 Correct 276 ms 34272 KB Output is correct
13 Correct 244 ms 34284 KB Output is correct
14 Correct 238 ms 34576 KB Output is correct
15 Correct 285 ms 35764 KB Output is correct
16 Correct 210 ms 34916 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 305 ms 31936 KB Output is correct
3 Incorrect 345 ms 32092 KB Output isn't correct
4 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 347 ms 32760 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 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 9 ms 9812 KB Output is correct
5 Incorrect 7 ms 9812 KB Output isn't correct
6 Halted 0 ms 0 KB -