oj.uz

Submission #418031

# Submission time Handle Problem Language Result Execution time Memory
418031 2021-06-04T22:35:07 Z Hegdahl Simurgh (IOI17_simurgh) C++17
0 / 100
 56 ms 284 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);
  for (int rep = 0; rep < 30'000; ++rep) {
    vector<ld> w = score;
    for (int i = 0; i < m; ++i) w[i] += rng()%1000;
    auto t = mst(w);
    int common = count_common_roads(t);

    for (int i : t) score[i] += (common-expect);
  }

  return mst(score);
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 204 KB correct
2 Correct 55 ms 276 KB correct
3 Correct 56 ms 284 KB correct
4 Incorrect 33 ms 204 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 204 KB correct
2 Correct 55 ms 276 KB correct
3 Correct 56 ms 284 KB correct
4 Incorrect 33 ms 204 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 204 KB correct
2 Correct 55 ms 276 KB correct
3 Correct 56 ms 284 KB correct
4 Incorrect 33 ms 204 KB WA in grader: NO
5 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 55 ms 204 KB correct
2 Correct 55 ms 276 KB correct
3 Correct 56 ms 284 KB correct
4 Incorrect 33 ms 204 KB WA in grader: NO
5 Halted 0 ms 0 KB -