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;
#define ll long long
mt19937 rng(time(0));
const ll nx=1e3+5;
ll ds[nx];
ll hv[nx], l[nx], sz[nx], rt, pa[nx], w[nx], t;
vector<pair<ll, ll>> k, rnd;
vector<ll> d[nx];
map<pair<ll, ll>, ll> mp;
ll dfssz(ll u)
{
sz[u]=1;
for (auto v:d[u]) sz[u]+=dfssz(v);
if (d[u].size()==1) hv[u]=d[u][0], l[u]=-1;
else if (d[u].size()==2)
{
if (sz[d[u][0]]<sz[d[u][1]]) swap(d[u][0], d[u][1]);
hv[u]=d[u][0];
l[u]=d[u][1];
}
return sz[u];
}
ll query(ll u, ll v)
{
if (u>v) swap(u, v);
if (mp.find({u, v})!=mp.end()) return mp[{u, v}];
return mp[{u, v}]=get_distance(u, v);
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
pair<ll, ll> mx;
for (ll i=2; i<=N; i++) rnd.push_back({rng(), i});
sort(rnd.begin(), rnd.end());
for (ll i=0; i<min(400, N); i++) mx=max(mx, {query(1, rnd[i].second), i});
rt=mx.second;
for (ll i=1; i<=N; i++) if (i!=rt) ds[i]=query(rt, i), k.push_back({ds[i], i});
sort(k.begin(), k.end());
for (auto [_, u]:k)
{
for (ll i=1; i<=N; i++) hv[i]=l[i]=-1;
dfssz(rt);
ll tmp=rt;
while (1)
{
while (hv[tmp]!=-1) tmp=hv[tmp];
ll ld=query(rt, tmp)-((query(rt, tmp)+query(rt, u))-query(u, tmp))/2;
while (ld!=0) ld-=w[tmp], tmp=pa[tmp];
if (d[tmp].size()<2)
{
d[tmp].push_back(u), pa[u]=tmp, w[u]=query(u, tmp), A[t]=u, B[t]=tmp, W[t++]=query(u, tmp);
break;
}
else tmp=l[tmp];
}
}
}
# | 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... |