Submission #586495

#	Time	Username	Problem	Language	Result	Execution time	Memory
586495		hibiki	City Mapping (NOI18_citymapping)	C++11	0 / 100	2 ms	1108 KiB

citymapping

#include "citymapping.h"
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()

long long has[1005][1005];
vector<pair<pair<int,int>,int> > ans;

long long ask(int a, int b)
{
	if(a > b) swap(a,b);
	if(a == b) return 0;
	if(has[a][b]) return has[a][b];
	return has[a][b] = get_distance(a, b);
}

void gen(int idx, vector<int> child)
{
	if(sz(child) == 0) return ;
	vector<pair<int,int> > dis, near;
	vector<int> n_child[10];
	for(auto c: child)
		dis.pb({ask(idx, c), c});
	sort(all(dis));
	near.pb(dis[0]);
	for(int i = 0; i < sz(dis); i++)
	{
		for(int j = 0; j < sz(near); j++)
		{
			if(near[j].s == dis[i].s) continue;
			int ret = ask(near[j].s, dis[i].s);
			if(ret + near[j].f == dis[i].f)
				n_child[j].pb(dis[i].s);
			else if(j == sz(near) - 1)
				near.pb(dis[i]);
		}
	}
	for(int i = 0; i < sz(near); i++)
	{
		auto val = near[i];
		ans.pb({{idx, val.s}, val.f});
		gen(val.s, n_child[i]);
	}
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	for (int i = 0; i < N - 1; i++) {
		A[i] = 1;
		B[i] = 2;
		W[i] = 1;
	}
	vector<int> temp;
	for(int i = 2; i <= N; i++)
		temp.pb(i);
	gen(1, temp);
	for(int i = 0; i < sz(ans); i++)
	{
		A[i] = ans[i].f.f;
		B[i] = ans[i].f.s;
		W[i] = ans[i].s;
	}
	return;
}

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