| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 93615 | admin | City Mapping (NOI18_citymapping) | C++17 | 0 ms | 0 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;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
vector<pll> lis;
ll di[1010][1010];
vector<pll> ttis[1010];
int par[1010];
ll calc(int u, int v) {
if (di[u][v]) return di[u][v];
if (u==v) return 0;
ll d = get_distance(u,v);
di[u][v] = di[v][u] = d;
return d;
}
int head, q;
int dir[1010][1010];
void add(int u, int v, int A[], int B[], int W[]) {
A[q] = u;
B[q] = v;
W[q] = calc(head,v)-calc(head,u);
par[v] = u;
ttis[u].push_back(pll(W[q],v));
int p = v;
while(p!=head) {
int pp = par[p];
for (int i=0;i<ttis[pp].size();i++) if (ttis[pp][i].second==p) {
dir[pp][v] = i;
break;
}
p = pp;
}
q++;
}
int D[1010], E[1010];
void dfs(int here) {
for (pll &tmp : ttis[here]) {
dfs(tmp.second);
}
if (ttis[here].empty()) {
D[here] = 0;
E[here] = here;
return;
}
if (ttis[here].size()==1) {
D[here]=D[ttis[here][0].second];
E[here]=E[ttis[here][0].second];
return;
}
int t = (D[ttis[here][0].second]>D[ttis[here][1].second]?0:1);
D[here]=max(D[ttis[here][t].second]-1,D[ttis[here][1-t].second]);
E[here]=E[ttis[here][t].second];
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
memset(par,-1,sizeof(par));
int i, j;
ll maxi = 0;
for (i=1;i<n;i++) {
if (maxi<calc(0,i)) {
maxi=calc(0,i);
head=i;
}
}
//printf("\n%d\n",head);
vector<pll> pis;
for (i=0;i<n;i++) {
//if (calc(head,i)+calc(0,i)==calc(0,head)) {
// pis.push_back(pll(calc(i,head),i));
//}
//else
lis.push_back(pll(calc(i,head),i));
}
//sort(pis.begin(),pis.end());
//for (j=1;j<pis.size();j++) {
// add(pis[j-1].second,pis[j].second);
//}
sort(lis.begin(),lis.end());
add(lis[0].second,lis[1].second,A,B,W);
for (j=2;j<lis.size();j++) {
dfs(lis[1].second);
int idx = lis[j].second;
ll mini = LINF;
int p = lis[1].second;
while(!ttis[p].empty()) {
ll d = (calc(head,idx)+calc(head,E[p])-calc(E[p],idx))/2;
int v = E[p];
while(calc(head,p)<d) {
p = ttis[p][dir[p][v]].second;
}
if (ttis[p].size()<=1) break;
p = ttis[p][1-dir[p][v]].second;
}
add(p,idx,A,B,W);
}
}