oj.uz

Submission #418033

# Submission time Handle Problem Language Result Execution time Memory
418033 2021-06-04T22:39:18 Z Hegdahl Simurgh (IOI17_simurgh) C++17
13 / 100
 3000 ms 332 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<ld> &w) {
  iota(boss, boss+n, 0);
  fill(under, under+n, 1);

  vector<int> eid(e.size());
  iota(eid.begin(), eid.end(), 0);
  sort(eid.begin(), eid.end(), [&](int i, int j) { return w[i] > w[j]; });

  vector<int> ans;
  for (int i : eid)
    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);
  for (int rep = 0; rep < 30'000; ++rep) {
    vector<ld> w(m);
    iota(w.begin(), w.end(), 0);
    shuffle(w.begin(), w.end(), rng);

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

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

  for (int i = 0; i < m; ++i)
    score[i] /= cnt[i];

  return mst(score);
}

Compilation message

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

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 204 KB correct
2 Correct 70 ms 204 KB correct
3 Correct 68 ms 324 KB correct
4 Correct 43 ms 204 KB correct
5 Correct 33 ms 204 KB correct
6 Correct 50 ms 276 KB correct
7 Correct 5 ms 204 KB correct
8 Correct 11 ms 204 KB correct
9 Correct 19 ms 300 KB correct
10 Correct 44 ms 204 KB correct
11 Correct 26 ms 276 KB correct
12 Correct 45 ms 204 KB correct
13 Correct 70 ms 288 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 204 KB correct
2 Correct 70 ms 204 KB correct
3 Correct 68 ms 324 KB correct
4 Correct 43 ms 204 KB correct
5 Correct 33 ms 204 KB correct
6 Correct 50 ms 276 KB correct
7 Correct 5 ms 204 KB correct
8 Correct 11 ms 204 KB correct
9 Correct 19 ms 300 KB correct
10 Correct 44 ms 204 KB correct
11 Correct 26 ms 276 KB correct
12 Correct 45 ms 204 KB correct
13 Correct 70 ms 288 KB correct
14 Execution timed out 3032 ms 332 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 204 KB correct
2 Correct 70 ms 204 KB correct
3 Correct 68 ms 324 KB correct
4 Correct 43 ms 204 KB correct
5 Correct 33 ms 204 KB correct
6 Correct 50 ms 276 KB correct
7 Correct 5 ms 204 KB correct
8 Correct 11 ms 204 KB correct
9 Correct 19 ms 300 KB correct
10 Correct 44 ms 204 KB correct
11 Correct 26 ms 276 KB correct
12 Correct 45 ms 204 KB correct
13 Correct 70 ms 288 KB correct
14 Execution timed out 3032 ms 332 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 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 68 ms 204 KB correct
2 Correct 70 ms 204 KB correct
3 Correct 68 ms 324 KB correct
4 Correct 43 ms 204 KB correct
5 Correct 33 ms 204 KB correct
6 Correct 50 ms 276 KB correct
7 Correct 5 ms 204 KB correct
8 Correct 11 ms 204 KB correct
9 Correct 19 ms 300 KB correct
10 Correct 44 ms 204 KB correct
11 Correct 26 ms 276 KB correct
12 Correct 45 ms 204 KB correct
13 Correct 70 ms 288 KB correct
14 Execution timed out 3032 ms 332 KB Time limit exceeded
15 Halted 0 ms 0 KB -