# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
963471 | Issa | City Mapping (NOI18_citymapping) | C++17 | 50 ms | 860 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"
const int maxn = 1e3 + 100;
const ll INF = (ll)1e18 + 100;
const int inf = 1e9 + 100;
const int MOD = 1e9 + 7;
const int maxl = 30;
const int P = 31;
long long get_distance(int X, int Y);
int n;
vector<int> g[maxn];
ll d[maxn][maxn];
vector<pii> ans;
int sz[maxn];
int mx[maxn];
void get(int v, int del){
sz[v] = 1; mx[v] = 0;
for(int to: g[v]){
if(to == del) continue;
get(to, del);
sz[v] += sz[to];
if(sz[to] > sz[mx[v]]) mx[v] = to;
}
}
void find_roads(int N, int Q, int A[], int B[], int W[]){
n = N;
vector<int> v;
for(int i = 2; i <= n; i++){
v.push_back(i);
d[1][i] = get_distance(1, i);
}
sort(v.begin(), v.end(), [](int i, int j){
return d[1][i] < d[1][j];
});
int edg = 0;
for(int i: v){
int r = 1, del = 0;
while(true){
get(r, del);
vector<int> s;
s.push_back(r);
while(mx[s.back()]){
s.push_back(mx[s.back()]);
}
if(s.size() == 1) break;
ll x = d[1][s.back()] + d[1][i] - get_distance(s.back(), i);
x /= 2; int j = 0;
while(d[1][s[j]] != x) j++;
r = s[j];
if(j + 1 < s.size()) del = s[j+1];
else del = 0;
}
A[edg] = r; B[edg] = i;
W[edg] = d[1][i] - d[1][r];
edg++; g[r].push_back(i);
}
}
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... |