| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 426443 | Amylopectin | City Mapping (NOI18_citymapping) | C++14 | 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 <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include "citymapping.h"
#include "grader.cpp"
using namespace std;
const int mxn = 1010;
struct we
{
int no,dis;
};
struct pat
{
int fr,to,dis;
};
bool cmp(const struct we &l,const struct we &r)
{
return l.dis < r.dis;
}
struct pat apa[mxn] = {};
int di[mxn][mxn] = {},li[mxn][mxn] = {},cli[mxn] = {},u[mxn] = {},ncli[mxn] = {},capa = 0;
//struct we fli[mxn] = {};
int re(int cn,int la)
{
if(cli[cn] == 0)
{
return 0;
}
if(cli[cn] == 1)
{
apa[capa] = {cn,li[cn][0],di[cn][li[cn][0]]};
capa ++;
return 0;
}
int i,fn,cma = -1,mno = -1,cou = 0,cva,cl,cr,mid,tn,nco = 0;
struct we fli[mxn] = {};
for(i=0; i<cli[cn]; i++)
{
fn = li[cn][i];
if(di[cn][fn] > cma)
{
cma = di[cn][fn];
mno = fn;
}
}
u[mno] = la;
for(i=0; i<cli[cn]; i++)
{
fn = li[cn][i];
if(fn == mno)
{
continue;
}
di[mno][fn] = get_distance(mno,fn);
if(di[mno][fn] + di[cn][fn] == di[cn][mno])
{
fli[cou] = {fn,di[cn][fn]};
cou ++;
u[fn] = la;
}
}
fli[cou] = {cn,0};
cou ++;
sort(fli,fli+cou,cmp);
fli[cou] = {mno,di[cn][mno]};
cou ++;
for(i=0; i<cli[cn]; i++)
{
fn = li[cn][i];
if(u[fn] == la)
{
continue;
}
cva = di[cn][fn] - (di[cn][fn] + di[mno][fn] - di[cn][mno]) / 2;
cl = 0;
cr = cou - 1;
while(cl < cr)
{
mid = (cl+cr) / 2;
if(fli[mid].dis >= cva)
{
cr = mid;
}
else
{
cl = mid+1;
}
}
tn = fli[cl].no;
di[tn][fn] = di[cn][fn] - di[cn][tn];
if(tn == cn)
{
li[tn][nco] = fn;
nco ++;
}
else
{
li[tn][cli[tn]] = fn;
cli[tn] ++;
}
}
cli[cn] = nco;
for(i=0; i<cou-1; i++)
{
fn = fli[i].no;
tn = fli[i+1].no;
apa[capa] = {fn,tn,di[cn][tn] - di[cn][fn]};
capa ++;
re(fn,la+1);
}
return 0;
}
void find_roads(int n, int q, int a[], int b[], int w[])
{
int i,j,stn = (rand() % n) + 1;
for(i=1; i<=n; i++)
{
if(i != stn)
{
di[stn][i] = get_distance(stn,i);
li[stn][cli[stn]] = i;
cli[stn] ++;
}
}
re(stn,1);
for(i=0; i<n-1; i++)
{
a[i] = apa[i].fr;
b[i] = apa[i].to;
w[i] = apa[i].dis;
}
// for (int i = 0; i < N - 1; i++)
// {
// A[i] = 1;
// B[i] = 2;
// W[i] = 1;
// }
return;
}
//int main()
//{
// int i,j,n,m;
// scanf("%d")
// return 0;
//}