Submission #1307160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307160		ayaz	Stranded Far From Home (BOI22_island)	C++20	0 / 100	1098 ms	45388 KiB

island

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#define line() "author : AyazN";
#endif

typedef long long ll;

#define all(x) (x).begin(), (x).end()
#define isz(x) (int)(x.size())
#define int ll

typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;

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

const int sz = 300500, inf = 1000000000;
const ll mod = 1000000007, INF = 1000000000000000000;
vi g[sz];
int a[sz], cnt[sz], col[sz], used[sz];
void precompute() {}
void dfs(int u) {
  used[u] = true;
  vi nodes;
  for (auto &v : g[u]) {
    if (used[v]) continue;
    if (cnt[col[v]] <= cnt[col[u]]) {
      cnt[col[u]] += cnt[col[v]];
      col[v] = col[u];
      nodes.push_back(v);
    }
  }
  for (auto &v : nodes) {
    dfs(v);
  }
  nodes.clear();
  for (auto &v : g[u]) {
    if (used[v]) continue;
    if (cnt[col[v]] <= cnt[col[u]]) {
      cnt[col[u]] += cnt[col[v]];
      col[v] = col[u];
      nodes.push_back(v);
    }
  }
  for (auto &v : nodes) {
    dfs(v);
  }
  
}
signed main() {
  cin.tie(nullptr);
#ifdef LOCAL
  // freopen("err.log", "w", stderr);
#endif
  precompute();
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; i++) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int u = 1; u <= n; u++) {
    sort(all(g[u]), [&](int i, int j) {
      return a[j] > a[i];
    });
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cnt[j] = a[j];
      col[j] = j;
      used[j] = 0;
    }
    dfs(i);
    auto ok = true;
    for (int j = 1; j <= n; j++) ok &= (col[j] == i);
    cout << ok;
  }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35