oj.uz

Submission #418034

# Submission time Handle Problem Language Result Execution time Memory
418034 2021-06-04T22:43:36 Z Hegdahl Simurgh (IOI17_simurgh) C++17
30 / 100
 2780 ms 1848 KB 
#include <bits/stdc++.h>
#include "simurgh.h"
#define ar array
using namespace std;
using ld = long double;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int mxN = 500;
int boss[mxN], under[mxN];

int find(int i) {
  return i == boss[i] ? i : boss[i] = find(boss[i]);
}

bool unite(int i, int j) {
  i = find(i), j = find(j);
  if (i == j) return false;
  if (under[i] < under[j]) swap(i, j);
  under[i] += under[j];
  boss[j] = i;
  return true;
}

int n;
vector<ar<int, 2>> e;


vector<int> mst(const vector<int> &ei) {
  iota(boss, boss+n, 0);
  fill(under, under+n, 1);

  vector<int> ans;
  for (int i : ei)
    if (unite(e[i][0], e[i][1]))
      ans.push_back(i);
  return ans;
}

vector<int> find_roads(int _n, vector<int> u, vector<int> v) {
  n = _n;
  const int m = u.size();
  e.resize(m);
  for (int mm = 0; mm < m; ++mm) e[mm] = {u[mm], v[mm]};

  ld expect = (ld)n/m;

  vector<ld> score(m, 1);
  vector<int> cnt(m, 1);

  vector<int> ei(m);
  iota(ei.begin(), ei.end(), 0);

  auto t0 = chrono::steady_clock::now();
  for (int rep = 0; rep < 30'000; ++rep) {
    shuffle(ei.begin(), ei.end(), rng);

    auto t = mst(ei);
    int common = count_common_roads(t);

    for (int i : t) score[i] += common, ++cnt[i];

    auto t1 = chrono::steady_clock::now();
    if (chrono::duration_cast<chrono::milliseconds>(t1-t0).count() > 2800) break;
  }

  sort(ei.begin(), ei.end(), [&](int i, int j) { return score[i]/cnt[i] > score[j]/cnt[j]; });

  return mst(ei);
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:46:6: warning: unused variable 'expect' [-Wunused-variable]
   46 |   ld expect = (ld)n/m;
      |      ^~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 204 KB correct
2 Correct 31 ms 204 KB correct
3 Correct 31 ms 204 KB correct
4 Correct 25 ms 296 KB correct
5 Correct 22 ms 296 KB correct
6 Correct 27 ms 296 KB correct
7 Correct 4 ms 204 KB correct
8 Correct 8 ms 204 KB correct
9 Correct 15 ms 300 KB correct
10 Correct 25 ms 296 KB correct
11 Correct 18 ms 296 KB correct
12 Correct 25 ms 296 KB correct
13 Correct 31 ms 204 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 204 KB correct
2 Correct 31 ms 204 KB correct
3 Correct 31 ms 204 KB correct
4 Correct 25 ms 296 KB correct
5 Correct 22 ms 296 KB correct
6 Correct 27 ms 296 KB correct
7 Correct 4 ms 204 KB correct
8 Correct 8 ms 204 KB correct
9 Correct 15 ms 300 KB correct
10 Correct 25 ms 296 KB correct
11 Correct 18 ms 296 KB correct
12 Correct 25 ms 296 KB correct
13 Correct 31 ms 204 KB correct
14 Correct 1000 ms 336 KB correct
15 Correct 997 ms 340 KB correct
16 Correct 997 ms 352 KB correct
17 Correct 829 ms 332 KB correct
18 Correct 373 ms 300 KB correct
19 Correct 850 ms 300 KB correct
20 Correct 805 ms 332 KB correct
21 Correct 756 ms 332 KB correct
22 Correct 621 ms 312 KB correct
23 Correct 567 ms 324 KB correct
24 Correct 548 ms 316 KB correct
25 Correct 163 ms 204 KB correct
26 Correct 550 ms 308 KB correct
27 Correct 566 ms 204 KB correct
28 Correct 309 ms 304 KB correct
29 Correct 205 ms 284 KB correct
30 Correct 558 ms 312 KB correct
31 Correct 556 ms 312 KB correct
32 Correct 558 ms 328 KB correct
33 Correct 559 ms 332 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 204 KB correct
2 Correct 31 ms 204 KB correct
3 Correct 31 ms 204 KB correct
4 Correct 25 ms 296 KB correct
5 Correct 22 ms 296 KB correct
6 Correct 27 ms 296 KB correct
7 Correct 4 ms 204 KB correct
8 Correct 8 ms 204 KB correct
9 Correct 15 ms 300 KB correct
10 Correct 25 ms 296 KB correct
11 Correct 18 ms 296 KB correct
12 Correct 25 ms 296 KB correct
13 Correct 31 ms 204 KB correct
14 Correct 1000 ms 336 KB correct
15 Correct 997 ms 340 KB correct
16 Correct 997 ms 352 KB correct
17 Correct 829 ms 332 KB correct
18 Correct 373 ms 300 KB correct
19 Correct 850 ms 300 KB correct
20 Correct 805 ms 332 KB correct
21 Correct 756 ms 332 KB correct
22 Correct 621 ms 312 KB correct
23 Correct 567 ms 324 KB correct
24 Correct 548 ms 316 KB correct
25 Correct 163 ms 204 KB correct
26 Correct 550 ms 308 KB correct
27 Correct 566 ms 204 KB correct
28 Correct 309 ms 304 KB correct
29 Correct 205 ms 284 KB correct
30 Correct 558 ms 312 KB correct
31 Correct 556 ms 312 KB correct
32 Correct 558 ms 328 KB correct
33 Correct 559 ms 332 KB correct
34 Incorrect 2780 ms 1848 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 204 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 204 KB correct
2 Correct 31 ms 204 KB correct
3 Correct 31 ms 204 KB correct
4 Correct 25 ms 296 KB correct
5 Correct 22 ms 296 KB correct
6 Correct 27 ms 296 KB correct
7 Correct 4 ms 204 KB correct
8 Correct 8 ms 204 KB correct
9 Correct 15 ms 300 KB correct
10 Correct 25 ms 296 KB correct
11 Correct 18 ms 296 KB correct
12 Correct 25 ms 296 KB correct
13 Correct 31 ms 204 KB correct
14 Correct 1000 ms 336 KB correct
15 Correct 997 ms 340 KB correct
16 Correct 997 ms 352 KB correct
17 Correct 829 ms 332 KB correct
18 Correct 373 ms 300 KB correct
19 Correct 850 ms 300 KB correct
20 Correct 805 ms 332 KB correct
21 Correct 756 ms 332 KB correct
22 Correct 621 ms 312 KB correct
23 Correct 567 ms 324 KB correct
24 Correct 548 ms 316 KB correct
25 Correct 163 ms 204 KB correct
26 Correct 550 ms 308 KB correct
27 Correct 566 ms 204 KB correct
28 Correct 309 ms 304 KB correct
29 Correct 205 ms 284 KB correct
30 Correct 558 ms 312 KB correct
31 Correct 556 ms 312 KB correct
32 Correct 558 ms 328 KB correct
33 Correct 559 ms 332 KB correct
34 Incorrect 2780 ms 1848 KB WA in grader: NO
35 Halted 0 ms 0 KB -