oj.uz

Submission #727577

# Submission time Handle Problem Language Result Execution time Memory
727577 2023-04-21T01:32:10 Z horiseun Stranded Far From Home (BOI22_island) C++11
0 / 100
 143 ms 18068 KB 
#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <random>
#include <string>
#include <cassert>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;

#define ll long long

int n, m, s[200005];
ll sm[200005];
vector<pair<ll, int>> ord;
vector<int> adj[200005];
bool ans[200005];

struct UnionFind {
    int par[200005], sz[200005];
    ll nx[200005];
    UnionFind() {
        for (int i = 0; i < 200005; i++) {
            par[i] = i;
            sz[i] = 1;
            nx[i] = 0;
        }
    }

    int find(int x) {
        return par[x] == x ? x : par[x] = find(par[x]);
    }

    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (sz[x] < sz[y]) swap(x, y);
            par[y] = x;
            sz[x] += sz[y];
            if (!nx[y] || s[nx[y]] == s[y]) nx[y] = x;
        }
    }
} uf;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        ord.push_back({s[i], i});
    }   
    sort(ord.begin(), ord.end());
    for (int i = 0, a, b; i < m; i++) {
        cin >> a >> b;
        if (make_pair(s[a], a) < make_pair(s[b], b)) swap(a, b);
        adj[a].push_back(b);
    }

    for (auto [v, i] : ord) {
        sm[i] = s[i];
        for (int j : adj[i]) {
            uf.merge(i, j);
        }
    }
    reverse(ord.begin(), ord.end());
    uf.nx[ord[0].second] = 0;
    ans[0] = 1;
    for (auto [v, i] : ord) {
        if (ans[uf.nx[i]] && sm[i] >= sm[uf.nx[i]]) {
            ans[i] = true;
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i];
    }
    cout << "\n";

}

Compilation message

island.cpp: In function 'int main()':
island.cpp:71:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |     for (auto [v, i] : ord) {
      |               ^
island.cpp:80:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |     for (auto [v, i] : ord) {
      |               ^

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

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