Submission #418035

#	Time	Username	Problem	Language	Result	Execution time	Memory
418035		Hegdahl	Simurgh (IOI17_simurgh)	C++17	30 / 100	2924 ms	1644 KiB

simurgh

#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 (stderr)

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 / 13
• Subtask 2: 17 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30