Submission #640280

#	Time	Username	Problem	Language	Result	Execution time	Memory
640280		makanhulia	Stranded Far From Home (BOI22_island)	C++17	0 / 100	174 ms	25572 KiB

island

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef long long ll;
// const ll mod = 1e9 + 7;
const ll MAXN = 1e6 + 5;
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define sc second
#define endl '\n'
#define gl                        ios_base::sync_with_stdio(0);   cin.tie(0);                     cout.tie(0)

int n, m;
vi par, s, r;
vll val;
vector<vi> g;

int fpar(int a)
{
  return par[a] = (par[a] == a ? a : fpar(par[a]));
}

void merge(int a, int b)
{
  a = fpar(a), b = fpar(b);
  if (a == b)
    return;
  if (r[a] < r[b])
    swap(a, b);
  if (r[a] == r[b])
    r[a]++;
  par[b] = a;
}

bool cmp(pii a, pii b)
{
  return max(s[a.fi], s[a.sc]) <= max(s[b.fi], s[b.sc]);
}

int main()
{
  gl;
  cin >> n >> m;
  s.resize(n + 1);
  for (int i = 1; i <= n; i++)
    cin >> s[i];

  vector<pii> e;
  for (int i = 0; i < m; i++)
  {
    int a, b;
    cin >> a >> b;
    e.pb({a, b});
  }

  sort(e.begin(), e.end(), cmp);

  g.resize(n + 1), val.resize(n + 1), par.resize(n + 1), r.resize(n + 1);

  for (int i = 1; i <= n; i++)
  {
    g[i].pb(i);
    val[i] = s[i];
    par[i] = i;
  }

  for (pii edge : e)
  {
    int a = edge.fi, b = edge.sc;
    int para = fpar(a), parb = fpar(b);
    if (para == parb)
      continue;
    merge(para, parb);
    int p = fpar(a);
    if (val[para] < s[b])
      swap(g[p], g[parb]);
    else if (val[parb] < s[a])
      swap(g[p], g[para]);
    else
    {
      if (g[para].size() < g[parb].size())
        swap(g[para], g[parb]);
      for (int x : g[parb])
        g[para].pb(x);
      swap(g[p], g[para]);
    }
    val[p] = val[para] + val[parb];
  }

  vector<bool> ans(n + 1);
  for (int v : g[fpar(1)])
    ans[v] = 1;
  for (int i = 1; i <= n; i++)
    cout << ans[i];
  cout << endl;
  return 0;
}

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