Submission #426459

#	Time	Username	Problem	Language	Result	Execution time	Memory
426459		Amylopectin	City Mapping (NOI18_citymapping)	C++14	100 / 100	9 ms	7500 KiB

citymapping

#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
{
    long long no,dis;
};
struct pat
{
    long long fr,to,dis;
};
bool cmp(const struct we &l,const struct we &r)
{
    return l.dis < r.dis;
}
struct pat apa[mxn] = {};
long long di[mxn][mxn] = {},li[mxn][mxn] = {},cli[mxn] = {},u[mxn] = {},ncli[mxn] = {},capa = 0;
//struct we fli[mxn] = {};
long long re(long long cn,long long 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;
    }
    long long 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;
//        }
//    }
//    mno = rand() % cli[cn];
    mno = (cli[cn] * 2) / 3;
    mno = li[cn][mno];
    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);
    }
    re(tn,la+1);
    return 0;
}
void find_roads(int n, int q, int a[], int b[], int w[])
{
    int i,j,stn = (rand() % n) + 1;
//    stn = 8;
    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 (stderr)

citymapping.cpp: In function 'long long int re(long long int, long long int)':
citymapping.cpp:36:20: warning: unused variable 'cma' [-Wunused-variable]
   36 |     long long i,fn,cma = -1,mno = -1,cou = 0,cva,cl,cr,mid,tn,nco = 0;
      |                    ^~~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:120:11: warning: unused variable 'j' [-Wunused-variable]
  120 |     int i,j,stn = (rand() % n) + 1;
      |           ^

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 43 / 43