Submission #418033

#	Time	Username	Problem	Language	Result	Execution time	Memory
418033		Hegdahl	Simurgh (IOI17_simurgh)	C++17	13 / 100	3032 ms	332 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<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 (stderr)

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