Submission #147064

#	Time	Username	Problem	Language	Result	Execution time	Memory
147064		dongwon0427	City Mapping (NOI18_citymapping)	C++14	0 / 100	44 ms	504 KiB

citymapping

#include "citymapping.h"
#include <iostream>
using namespace std;
typedef long long ll;

ll dis[1005];

int dnccnt;
int color[1005];

int *A, *B, *W;
void dnc(int idx,int n) {
    int minidx = -1, mn=0;
    for(int i=1;i<=n;i++) {
        if(color[i] == color[idx] && i != idx) {
            ll tmp = get_distance(idx, i);
            dis[i] = tmp;
            if(minidx == -1 || mn > tmp) {
                minidx = i;
                mn = tmp;
            }
        }
    }
    if(minidx == -1) {
        return;
    }
    A[dnccnt] = idx;
    B[dnccnt] = minidx;
    W[dnccnt] = mn;

    dnccnt++;
    for(int i=1;i<=n;i++) {
        if(color[i] == color[idx]) {
            if(get_distance(minidx, i) + mn == dis[i]) {
                color[i] = dnccnt;
            }
        }
    }
    dnc(idx,n);
    dnc(minidx,n);
}
void find_roads(int n, int q, int a[], int b[], int w[]) {
	A=a, B=b, W=w;
	dnc(1,n);

	//for(int i=0;i<n-1;i++) cout<<a[i]<<' '<<b[i]<<' '<<w[i]<<'\n';

}

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