#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;
//}
Compilation message
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:116:11: warning: unused variable 'j' [-Wunused-variable]
116 | int i,j,stn = (rand() % n) + 1;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
480 KB |
Correct: 2414 out of 500000 queries used. |
2 |
Correct |
4 ms |
4308 KB |
Correct: 2292 out of 500000 queries used. |
3 |
Correct |
3 ms |
4684 KB |
Correct: 4838 out of 500000 queries used. |
4 |
Correct |
6 ms |
5592 KB |
Correct: 4942 out of 500000 queries used. |
5 |
Correct |
3 ms |
1100 KB |
Correct: 2933 out of 500000 queries used. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
480 KB |
Correct: 2414 out of 500000 queries used. |
2 |
Correct |
4 ms |
4308 KB |
Correct: 2292 out of 500000 queries used. |
3 |
Correct |
3 ms |
4684 KB |
Correct: 4838 out of 500000 queries used. |
4 |
Correct |
6 ms |
5592 KB |
Correct: 4942 out of 500000 queries used. |
5 |
Correct |
3 ms |
1100 KB |
Correct: 2933 out of 500000 queries used. |
6 |
Incorrect |
2 ms |
716 KB |
Reported list of edges differ from actual. |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
460 KB |
Correct: 2226 out of 12000 queries used. |
2 |
Correct |
2 ms |
460 KB |
Correct: 2228 out of 12000 queries used. |
3 |
Correct |
2 ms |
460 KB |
Correct: 2143 out of 12000 queries used. |
4 |
Correct |
2 ms |
472 KB |
Correct: 2443 out of 12000 queries used. |
5 |
Correct |
4 ms |
460 KB |
Correct: 2406 out of 12000 queries used. |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
460 KB |
Correct: 2226 out of 12000 queries used. |
2 |
Correct |
2 ms |
460 KB |
Correct: 2228 out of 12000 queries used. |
3 |
Correct |
2 ms |
460 KB |
Correct: 2143 out of 12000 queries used. |
4 |
Correct |
2 ms |
472 KB |
Correct: 2443 out of 12000 queries used. |
5 |
Correct |
4 ms |
460 KB |
Correct: 2406 out of 12000 queries used. |
6 |
Incorrect |
3 ms |
640 KB |
Reported list of edges differ from actual. |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
480 KB |
Correct: 2414 out of 500000 queries used. |
2 |
Correct |
4 ms |
4308 KB |
Correct: 2292 out of 500000 queries used. |
3 |
Correct |
3 ms |
4684 KB |
Correct: 4838 out of 500000 queries used. |
4 |
Correct |
6 ms |
5592 KB |
Correct: 4942 out of 500000 queries used. |
5 |
Correct |
3 ms |
1100 KB |
Correct: 2933 out of 500000 queries used. |
6 |
Incorrect |
2 ms |
716 KB |
Reported list of edges differ from actual. |
7 |
Halted |
0 ms |
0 KB |
- |