# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
200605 | wilwxk | City Mapping (NOI18_citymapping) | C++14 | 15 ms | 7032 KiB |
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 "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e3+5;
ll dist[MAXN][MAXN];
vector<tuple<int, int, int> > ans;
vector<int> subtree[MAXN];
mt19937 rng(time(0));
int n;
ll query(int a, int b) {
if(a == b) return 0;
if(a > b) swap(a, b);
if(dist[a][b]) return dist[a][b];
// printf("query %d %d\n", a, b);
return dist[a][b] = get_distance(a, b);
}
void solve(int cur) {
if(subtree[cur].size() == 1) return;
int x = rng()%int(subtree[cur].size());
x = subtree[cur][x];
printf("solve %d >> %d\n", cur, x); for(auto vertex : subtree[cur]) printf("%d ", vertex); cout << endl;
int mni; ll mn = 1e18;
for(auto vertex : subtree[cur]) if(vertex != x && query(x, vertex) < mn) mn = query(x, vertex), mni = vertex;
ans.push_back({x, mni, query(x, mni)});
Compilation message (stderr)
# | 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... |