oj.uz

Submission #586505

# Submission time Handle Problem Language Result Execution time Memory
586505 2022-06-30T10:57:04 Z hibiki City Mapping (NOI18_citymapping) C++11
9 / 100
 76 ms 11524 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(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));
	for(int i = 0; i < sz(dis); i++)
	{
		vector<pair<int,int> > temp;
		temp.pb({ask(idx, dis[i].s), -1});
		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);
			temp.pb({ret, j});
		}
		sort(all(temp));
		if(temp[0].s == -1)
			near.pb(dis[i]);
		else
			n_child[temp[0].s].pb(dis[i].s);

	}
	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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 10440 KB Correct: 251941 out of 500000 queries used.
2 Correct 76 ms 11524 KB Correct: 398952 out of 500000 queries used.
3 Correct 10 ms 7372 KB Correct: 32585 out of 500000 queries used.
4 Correct 11 ms 7156 KB Correct: 28235 out of 500000 queries used.
5 Correct 14 ms 7636 KB Correct: 48126 out of 500000 queries used.

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 10440 KB Correct: 251941 out of 500000 queries used.
2 Correct 76 ms 11524 KB Correct: 398952 out of 500000 queries used.
3 Correct 10 ms 7372 KB Correct: 32585 out of 500000 queries used.
4 Correct 11 ms 7156 KB Correct: 28235 out of 500000 queries used.
5 Correct 14 ms 7636 KB Correct: 48126 out of 500000 queries used.
6 Runtime error 11 ms 5600 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 7124 KB Too many calls to get_distance().
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 7124 KB Too many calls to get_distance().
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 10440 KB Correct: 251941 out of 500000 queries used.
2 Correct 76 ms 11524 KB Correct: 398952 out of 500000 queries used.
3 Correct 10 ms 7372 KB Correct: 32585 out of 500000 queries used.
4 Correct 11 ms 7156 KB Correct: 28235 out of 500000 queries used.
5 Correct 14 ms 7636 KB Correct: 48126 out of 500000 queries used.
6 Runtime error 11 ms 5600 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -