oj.uz

Submission #640280

# Submission time Handle Problem Language Result Execution time Memory
640280 2022-09-14T05:40:26 Z makanhulia Stranded Far From Home (BOI22_island) C++17
0 / 100
 174 ms 25572 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 232 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Runtime error 1 ms 468 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 55 ms 5460 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 144 ms 20896 KB Output is correct
3 Correct 174 ms 25572 KB Output is correct
4 Runtime error 56 ms 9928 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 58 ms 5468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 232 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Runtime error 1 ms 468 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -