Submission #642324

#	Time	Username	Problem	Language	Result	Execution time	Memory
642324		andecaandeci	Stranded Far From Home (BOI22_island)	C++17	100 / 100	317 ms	42624 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);
  set<int> st;
  for (int i = 1; i <= n; i++)
  {
    cin >> s[i];
    st.insert(s[i]);
  }

  vi v(st.begin(), st.end());
  vector<vector<pii>> e(v.size() + 1);

  for (int i = 0; i < m; i++)
  {
    int a, b;
    cin >> a >> b;
    e[lb(v.begin(), v.end(), max(s[a], s[b])) - v.begin()].push_back({a, b});
  }

  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 (int i = 0; i < v.size(); i++)
  {
    for (pii edge : e[i])
    {
      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, 0);
  for (int v : g[fpar(1)])
    ans[v] = 1;
  for (int i = 1; i <= n; i++)
    cout << ans[i];
  cout << endl;
  return 0;
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for (int i = 0; i < v.size(); i++)
      |                   ~~^~~~~~~~~~

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