oj.uz

Submission #963369

# Submission time Handle Problem Language Result Execution time Memory
963369 2024-04-14T22:03:25 Z Spade1 Stranded Far From Home (BOI22_island) C++14
10 / 100
 183 ms 32304 KB 
#pragma once
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef vector<vi> vvi;
typedef tuple<int, int, int> t3;
typedef tuple<int, int, int, int> t4;

template<typename T> using pq = priority_queue<T>;
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()
#define ins insert
#define int ll

template<typename T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1e9 + 7;
const int INF = 0x3fffffff;
const ll LINF = 0x1fffffffffffffff;
const char nl = '\n';
const int MX = 2e5 + 3;

ll s[MX], ans[MX], sz[MX], rep[MX];
vi adj[MX];
vector<t3> edges;

int f(int i) {return rep[i] == i ? i : rep[i] = f(rep[i]);}

void mark(int i) {
  ans[i] = 0;
  for (auto j : adj[i]) {
    if (f(j) == f(i) && ans[j] != 0) mark(j);
  }
}

void solve() {
  int n, m; cin >> n >> m;
  for (int i = 1; i <= n; ++i) ans[i] = 1, rep[i] = i;
  for (int i = 1; i <= n; ++i) cin >> s[i], sz[i] = s[i];
  for (int i = 1; i <= m; ++i) {
    int u, v; cin >> u >> v;
    adj[u].pb(v); adj[v].pb(u);
    edges.pb({max(s[u], s[v]), u, v});
  }
  sort(all(edges));
  for (auto [M, u, v] : edges) {
    int fu = f(u), fv = f(v);
    if (fu == fv) continue;
    if (s[u] > sz[fv]) mark(v);
    if (s[v] > sz[fu]) mark(u);
    sz[fu] += sz[fv];
    rep[fv] = rep[fu];
  }
  for (int i = 1; i <= n; ++i) cout << ans[i];
  cout << nl;
}

signed main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0); cin.tie(NULL);
  int t = 1;
  // cin >> t;
  while (t--) { solve(); }
  return 0;
}

Compilation message

island.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
island.cpp: In function 'void solve()':
island.cpp:69:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |   for (auto [M, u, v] : edges) {
      |             ^
island.cpp: At global scope:
island.cpp:81:8: warning: first argument of 'int main(ll, char**)' should be 'int' [-Wmain]
   81 | signed main(int argc, char* argv[]) {
      |        ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Incorrect 3 ms 10940 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 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 120 ms 24636 KB Output is correct
4 Correct 111 ms 26532 KB Output is correct
5 Correct 115 ms 24124 KB Output is correct
6 Correct 115 ms 24568 KB Output is correct
7 Correct 124 ms 24884 KB Output is correct
8 Correct 134 ms 25100 KB Output is correct
9 Correct 102 ms 24324 KB Output is correct
10 Correct 90 ms 24864 KB Output is correct
11 Correct 85 ms 24256 KB Output is correct
12 Correct 168 ms 23596 KB Output is correct
13 Correct 114 ms 32304 KB Output is correct
14 Correct 127 ms 31776 KB Output is correct
15 Correct 103 ms 24436 KB Output is correct
16 Correct 64 ms 23732 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Incorrect 117 ms 24384 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 10844 KB Output is correct
2 Incorrect 183 ms 24752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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