oj.uz

Submission #963370

# Submission time Handle Problem Language Result Execution time Memory
963370 2024-04-14T22:04:56 Z Spade1 Stranded Far From Home (BOI22_island) C++14
10 / 100
 152 ms 29688 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 (M > sz[fv]) mark(v);
    if (M > 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 3 ms 10844 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Incorrect 3 ms 10844 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 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 101 ms 21008 KB Output is correct
4 Correct 152 ms 23548 KB Output is correct
5 Correct 97 ms 19852 KB Output is correct
6 Correct 119 ms 21012 KB Output is correct
7 Correct 108 ms 20216 KB Output is correct
8 Correct 103 ms 20892 KB Output is correct
9 Correct 112 ms 20076 KB Output is correct
10 Correct 109 ms 20892 KB Output is correct
11 Correct 83 ms 20844 KB Output is correct
12 Correct 120 ms 20104 KB Output is correct
13 Correct 131 ms 29688 KB Output is correct
14 Correct 126 ms 28576 KB Output is correct
15 Correct 103 ms 20944 KB Output is correct
16 Correct 66 ms 20524 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 137 ms 20096 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 128 ms 20252 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 10844 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Incorrect 3 ms 10844 KB Output isn't correct
5 Halted 0 ms 0 KB -