This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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() > 2800) 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;
| ^~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |