oj.uz

Submission #640284

# Submission time Handle Problem Language Result Execution time Memory
640284 2022-09-14T05:48:41 Z kebine Stranded Far From Home (BOI22_island) C++17
100 / 100
 310 ms 42580 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);
  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);
  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

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.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 212 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct

Subtask #2
10.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 208 ms 35740 KB Output is correct
4 Correct 131 ms 23936 KB Output is correct
5 Correct 219 ms 36172 KB Output is correct
6 Correct 221 ms 33084 KB Output is correct
7 Correct 233 ms 37224 KB Output is correct
8 Correct 137 ms 22512 KB Output is correct
9 Correct 181 ms 33548 KB Output is correct
10 Correct 125 ms 28168 KB Output is correct
11 Correct 93 ms 18712 KB Output is correct
12 Correct 122 ms 19016 KB Output is correct
13 Correct 128 ms 25228 KB Output is correct
14 Correct 127 ms 24700 KB Output is correct
15 Correct 192 ms 37492 KB Output is correct
16 Correct 142 ms 37088 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 310 ms 37860 KB Output is correct
3 Correct 253 ms 34092 KB Output is correct
4 Correct 141 ms 25104 KB Output is correct
5 Correct 138 ms 27972 KB Output is correct
6 Correct 307 ms 42552 KB Output is correct
7 Correct 193 ms 42044 KB Output is correct
8 Correct 204 ms 41912 KB Output is correct
9 Correct 148 ms 40792 KB Output is correct
10 Correct 171 ms 32060 KB Output is correct
11 Correct 132 ms 25556 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 128 ms 18704 KB Output is correct
3 Correct 129 ms 23528 KB Output is correct
4 Correct 137 ms 24864 KB Output is correct
5 Correct 133 ms 26160 KB Output is correct
6 Correct 130 ms 23760 KB Output is correct
7 Correct 109 ms 23104 KB Output is correct
8 Correct 72 ms 21548 KB Output is correct
9 Correct 70 ms 13024 KB Output is correct
10 Correct 137 ms 25580 KB Output is correct
11 Correct 122 ms 25000 KB Output is correct

Subtask #5
35.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 212 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 208 ms 35740 KB Output is correct
18 Correct 131 ms 23936 KB Output is correct
19 Correct 219 ms 36172 KB Output is correct
20 Correct 221 ms 33084 KB Output is correct
21 Correct 233 ms 37224 KB Output is correct
22 Correct 137 ms 22512 KB Output is correct
23 Correct 181 ms 33548 KB Output is correct
24 Correct 125 ms 28168 KB Output is correct
25 Correct 93 ms 18712 KB Output is correct
26 Correct 122 ms 19016 KB Output is correct
27 Correct 128 ms 25228 KB Output is correct
28 Correct 127 ms 24700 KB Output is correct
29 Correct 192 ms 37492 KB Output is correct
30 Correct 142 ms 37088 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 310 ms 37860 KB Output is correct
33 Correct 253 ms 34092 KB Output is correct
34 Correct 141 ms 25104 KB Output is correct
35 Correct 138 ms 27972 KB Output is correct
36 Correct 307 ms 42552 KB Output is correct
37 Correct 193 ms 42044 KB Output is correct
38 Correct 204 ms 41912 KB Output is correct
39 Correct 148 ms 40792 KB Output is correct
40 Correct 171 ms 32060 KB Output is correct
41 Correct 132 ms 25556 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 128 ms 18704 KB Output is correct
44 Correct 129 ms 23528 KB Output is correct
45 Correct 137 ms 24864 KB Output is correct
46 Correct 133 ms 26160 KB Output is correct
47 Correct 130 ms 23760 KB Output is correct
48 Correct 109 ms 23104 KB Output is correct
49 Correct 72 ms 21548 KB Output is correct
50 Correct 70 ms 13024 KB Output is correct
51 Correct 137 ms 25580 KB Output is correct
52 Correct 122 ms 25000 KB Output is correct
53 Correct 1 ms 320 KB Output is correct
54 Correct 1 ms 212 KB Output is correct
55 Correct 0 ms 212 KB Output is correct
56 Correct 2 ms 596 KB Output is correct
57 Correct 2 ms 596 KB Output is correct
58 Correct 1 ms 468 KB Output is correct
59 Correct 2 ms 588 KB Output is correct
60 Correct 1 ms 468 KB Output is correct
61 Correct 1 ms 460 KB Output is correct
62 Correct 2 ms 596 KB Output is correct
63 Correct 2 ms 712 KB Output is correct
64 Correct 2 ms 596 KB Output is correct
65 Correct 1 ms 468 KB Output is correct
66 Correct 1 ms 460 KB Output is correct
67 Correct 193 ms 40164 KB Output is correct
68 Correct 132 ms 26948 KB Output is correct
69 Correct 225 ms 40448 KB Output is correct
70 Correct 207 ms 37432 KB Output is correct
71 Correct 225 ms 41712 KB Output is correct
72 Correct 136 ms 26948 KB Output is correct
73 Correct 192 ms 37892 KB Output is correct
74 Correct 127 ms 31700 KB Output is correct
75 Correct 95 ms 22132 KB Output is correct
76 Correct 121 ms 21996 KB Output is correct
77 Correct 125 ms 28156 KB Output is correct
78 Correct 119 ms 27824 KB Output is correct
79 Correct 198 ms 41908 KB Output is correct
80 Correct 164 ms 40760 KB Output is correct
81 Correct 300 ms 42344 KB Output is correct
82 Correct 243 ms 38576 KB Output is correct
83 Correct 141 ms 29532 KB Output is correct
84 Correct 124 ms 27940 KB Output is correct
85 Correct 297 ms 42580 KB Output is correct
86 Correct 210 ms 41972 KB Output is correct
87 Correct 194 ms 41936 KB Output is correct
88 Correct 162 ms 32088 KB Output is correct
89 Correct 126 ms 25688 KB Output is correct
90 Correct 134 ms 23232 KB Output is correct
91 Correct 121 ms 23500 KB Output is correct
92 Correct 127 ms 24864 KB Output is correct
93 Correct 130 ms 26180 KB Output is correct
94 Correct 123 ms 23956 KB Output is correct
95 Correct 99 ms 23068 KB Output is correct
96 Correct 73 ms 21452 KB Output is correct
97 Correct 62 ms 12992 KB Output is correct
98 Correct 126 ms 25456 KB Output is correct
99 Correct 115 ms 24968 KB Output is correct
100 Correct 46 ms 5256 KB Output is correct
101 Correct 264 ms 36860 KB Output is correct
102 Correct 108 ms 19956 KB Output is correct
103 Correct 231 ms 30420 KB Output is correct
104 Correct 283 ms 39428 KB Output is correct