oj.uz

Submission #963376

# Submission time Handle Problem Language Result Execution time Memory
963376 2024-04-14T22:20:57 Z Spade1 Stranded Far From Home (BOI22_island) C++14
10 / 100
 176 ms 43664 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], adj2[MX];
vector<t3> edges;

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

void mark(int i, int prt, int v) {
  ans[i] = v;
  for (auto j : adj2[i]) {
    if (j == prt) continue;
    if (ans[j] == 0) mark(j, i, 0);
    else mark(j, i, v);
  }
}

void solve() {
  int n, m; cin >> n >> m;
  int mx = 0;
  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];
    if (s[mx] < s[i]) mx = 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;
    adj2[u].pb(v); adj2[v].pb(u);
    if (s[u] > sz[fv]) ans[v] = 0;
    if (s[v] > sz[fu]) ans[u] = 0;
    sz[fu] += sz[fv];
    rep[fv] = rep[fu];
  }
  mark(mx, 0, 1);
  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:75:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |   for (auto [M, u, v] : edges) {
      |             ^
island.cpp: At global scope:
island.cpp:89:8: warning: first argument of 'int main(ll, char**)' should be 'int' [-Wmain]
   89 | signed main(int argc, char* argv[]) {
      |        ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct
3 Correct 6 ms 9820 KB Output is correct
4 Incorrect 5 ms 9820 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 4 ms 9820 KB Output is correct
2 Correct 5 ms 9816 KB Output is correct
3 Correct 161 ms 36100 KB Output is correct
4 Correct 121 ms 36052 KB Output is correct
5 Correct 164 ms 30564 KB Output is correct
6 Correct 168 ms 31212 KB Output is correct
7 Correct 145 ms 31300 KB Output is correct
8 Correct 162 ms 31224 KB Output is correct
9 Correct 145 ms 30956 KB Output is correct
10 Correct 129 ms 32632 KB Output is correct
11 Correct 99 ms 32700 KB Output is correct
12 Correct 176 ms 31228 KB Output is correct
13 Correct 120 ms 43476 KB Output is correct
14 Correct 124 ms 43516 KB Output is correct
15 Correct 133 ms 43664 KB Output is correct
16 Correct 90 ms 43260 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Incorrect 175 ms 31168 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 9820 KB Output is correct
2 Correct 6 ms 9820 KB Output is correct
3 Correct 6 ms 9820 KB Output is correct
4 Incorrect 5 ms 9820 KB Output isn't correct
5 Halted 0 ms 0 KB -