oj.uz

Submission #586486

# Submission time Handle Problem Language Result Execution time Memory
586486 2022-06-30T10:35:56 Z hibiki City Mapping (NOI18_citymapping) C++11
0 / 100
 2 ms 1108 KB 
#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(has[a][b]) return has[a][b];
	return has[a][b] = get_distance(a, b);
}

void gen(int idx, vector<int> child)
{
	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 = 1; i < sz(dis); i++)
	{
		for(int j = 0; j < sz(near); j++)
		{
			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);
	return;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 980 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 980 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 980 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -