oj.uz

답안 #418035

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
418035 2021-06-04T22:44:55 Z Hegdahl Simurgh (IOI17_simurgh) C++17
30 / 100
 2924 ms 1644 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() > 2950) 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

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 284 KB correct
2 Correct 31 ms 276 KB correct
3 Correct 31 ms 204 KB correct
4 Correct 26 ms 204 KB correct
5 Correct 23 ms 204 KB correct
6 Correct 28 ms 276 KB correct
7 Correct 4 ms 204 KB correct
8 Correct 8 ms 288 KB correct
9 Correct 15 ms 292 KB correct
10 Correct 27 ms 296 KB correct
11 Correct 18 ms 288 KB correct
12 Correct 25 ms 296 KB correct
13 Correct 31 ms 204 KB correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 284 KB correct
2 Correct 31 ms 276 KB correct
3 Correct 31 ms 204 KB correct
4 Correct 26 ms 204 KB correct
5 Correct 23 ms 204 KB correct
6 Correct 28 ms 276 KB correct
7 Correct 4 ms 204 KB correct
8 Correct 8 ms 288 KB correct
9 Correct 15 ms 292 KB correct
10 Correct 27 ms 296 KB correct
11 Correct 18 ms 288 KB correct
12 Correct 25 ms 296 KB correct
13 Correct 31 ms 204 KB correct
14 Correct 1008 ms 340 KB correct
15 Correct 1020 ms 336 KB correct
16 Correct 1000 ms 336 KB correct
17 Correct 857 ms 332 KB correct
18 Correct 382 ms 292 KB correct
19 Correct 892 ms 332 KB correct
20 Correct 818 ms 332 KB correct
21 Correct 776 ms 332 KB correct
22 Correct 618 ms 308 KB correct
23 Correct 587 ms 304 KB correct
24 Correct 552 ms 300 KB correct
25 Correct 164 ms 204 KB correct
26 Correct 553 ms 304 KB correct
27 Correct 571 ms 304 KB correct
28 Correct 313 ms 288 KB correct
29 Correct 205 ms 284 KB correct
30 Correct 572 ms 304 KB correct
31 Correct 564 ms 308 KB correct
32 Correct 564 ms 324 KB correct
33 Correct 568 ms 308 KB correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 284 KB correct
2 Correct 31 ms 276 KB correct
3 Correct 31 ms 204 KB correct
4 Correct 26 ms 204 KB correct
5 Correct 23 ms 204 KB correct
6 Correct 28 ms 276 KB correct
7 Correct 4 ms 204 KB correct
8 Correct 8 ms 288 KB correct
9 Correct 15 ms 292 KB correct
10 Correct 27 ms 296 KB correct
11 Correct 18 ms 288 KB correct
12 Correct 25 ms 296 KB correct
13 Correct 31 ms 204 KB correct
14 Correct 1008 ms 340 KB correct
15 Correct 1020 ms 336 KB correct
16 Correct 1000 ms 336 KB correct
17 Correct 857 ms 332 KB correct
18 Correct 382 ms 292 KB correct
19 Correct 892 ms 332 KB correct
20 Correct 818 ms 332 KB correct
21 Correct 776 ms 332 KB correct
22 Correct 618 ms 308 KB correct
23 Correct 587 ms 304 KB correct
24 Correct 552 ms 300 KB correct
25 Correct 164 ms 204 KB correct
26 Correct 553 ms 304 KB correct
27 Correct 571 ms 304 KB correct
28 Correct 313 ms 288 KB correct
29 Correct 205 ms 284 KB correct
30 Correct 572 ms 304 KB correct
31 Correct 564 ms 308 KB correct
32 Correct 564 ms 324 KB correct
33 Correct 568 ms 308 KB correct
34 Incorrect 2924 ms 1644 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 204 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 284 KB correct
2 Correct 31 ms 276 KB correct
3 Correct 31 ms 204 KB correct
4 Correct 26 ms 204 KB correct
5 Correct 23 ms 204 KB correct
6 Correct 28 ms 276 KB correct
7 Correct 4 ms 204 KB correct
8 Correct 8 ms 288 KB correct
9 Correct 15 ms 292 KB correct
10 Correct 27 ms 296 KB correct
11 Correct 18 ms 288 KB correct
12 Correct 25 ms 296 KB correct
13 Correct 31 ms 204 KB correct
14 Correct 1008 ms 340 KB correct
15 Correct 1020 ms 336 KB correct
16 Correct 1000 ms 336 KB correct
17 Correct 857 ms 332 KB correct
18 Correct 382 ms 292 KB correct
19 Correct 892 ms 332 KB correct
20 Correct 818 ms 332 KB correct
21 Correct 776 ms 332 KB correct
22 Correct 618 ms 308 KB correct
23 Correct 587 ms 304 KB correct
24 Correct 552 ms 300 KB correct
25 Correct 164 ms 204 KB correct
26 Correct 553 ms 304 KB correct
27 Correct 571 ms 304 KB correct
28 Correct 313 ms 288 KB correct
29 Correct 205 ms 284 KB correct
30 Correct 572 ms 304 KB correct
31 Correct 564 ms 308 KB correct
32 Correct 564 ms 324 KB correct
33 Correct 568 ms 308 KB correct
34 Incorrect 2924 ms 1644 KB WA in grader: NO
35 Halted 0 ms 0 KB -