Submission #1287071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287071		khoi281109	Sirni (COCI17_sirni)	C++20	140 / 140	1080 ms	378800 KiB

sirni

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

#define ii make_pair

const int maxN = 1e5 + 5; const int maxM = 1e7 + 5;

int n, a[maxM], connect[maxM], pre[maxM], max1, d;

long long dist;

vector < pair < int, int > > vect[maxM];

int get(int x)

{

     return x == connect[x] ? x : connect[x] = get(connect[x]);

}

int main()

{

     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

     cin >> n;

     for (int i = 1; i <= n; i++) cin >> a[i], max1 = max(max1, a[i]);

     sort(a + 1, a + 1 + n);

     n = unique(a + 1, a + 1 + n) - a + 1;

     for (int i = 1; i <= max1; i++) connect[i] = i;

     for (int i = 1; i <= n; i++) pre[a[i]] = a[i];

     for (int i = max1; i >= 1; i--) if (!pre[i]) pre[i] = pre[i + 1];

     for (int i = 1; i <= n; i++)

     {

          int t = a[i]; int p = pre[t + 1];

          if (p && p - t < t) vect[p - t].push_back(ii(t, p));

          for (int j = t << 1; j <= max1; j += a[i])

          {

               int z = pre[j];

               if (z == 0) break;

               if (z - j < t) vect[z - j].push_back(ii(t, z));

          }

     }

     for (int i = 0; i <= max1; i++)

          for (auto e: vect[i])

          {

               int x = get(e.first); int y = get(e.second);

               if (x == y) continue;

               dist += i;

               connect[x] = y; d++;

               if (d == n - 1) break;

          }

     cout << dist;

}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14