oj.uz

답안 #586367

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
586367 2022-06-30T07:50:07 Z Jomnoi City Mapping (NOI18_citymapping) C++17
57 / 100
 129 ms 24656 KB 
#include <bits/stdc++.h>
#include "citymapping.h"
using namespace std;

const int MAX_N = 1005;

long long dist[MAX_N][MAX_N];
vector <pair <long long, int>> graph[MAX_N];
vector <tuple <int, int, int>> tree;
bool visited[MAX_N];

void dfs(int u, int p) {
	visited[u] = true;
	if(p != -1) {
		tree.emplace_back(u, p, dist[u][p]);
	}
	for(auto [w, v] : graph[u]) {
		if(visited[v] == true) {
			continue;
		}

		if(p == -1) {
			dfs(v, u);
		}
		else {
			if(dist[v][u] + dist[u][p] == dist[v][p]) {
				dfs(v, u);
			}
		}
	}
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	if(Q == 500000) {
		for(int i = 1; i <= N; i++) {
			for(int j = i + 1; j <= N; j++) {
				dist[i][j] = dist[j][i] = get_distance(i, j);
				graph[i].emplace_back(dist[i][j], j);
				graph[j].emplace_back(dist[j][i], i);
			}
		}

		for(int i = 1; i <= N; i++) {
			sort(graph[i].begin(), graph[i].end());
		}

		dfs(1, -1);
		
		for(int i = 0; i < N - 1; i++) {
			A[i] = get <0> (tree[i]);
			B[i] = get <1> (tree[i]);
			W[i] = get <2> (tree[i]);
		}
	}
	else if(Q == 12000) {
		int node = 1;
		long long furthest = 0;
		for(int i = 2; i <= N; i++) {
			dist[1][i] = get_distance(1, i);
			if(furthest < dist[1][i]) {
				furthest = dist[1][i];
				node = i;
			}
		}

		vector <pair <long long, int>> adj;
		for(int i = 1; i <= N; i++) {
			if(i == node) {
				continue;
			}

			dist[node][i] = get_distance(node, i);
			adj.emplace_back(dist[node][i], i);
		}

		sort(adj.begin(), adj.end());

		int prv = node, M = 0;
		long long prvDist = 0;
		for(auto [nowDist, now] : adj) {
			A[M] = prv;
			B[M] = now;
			W[M] = nowDist - prvDist;
			M++;
			
			prvDist = nowDist;
			prv = now;
		}
	}
	else {
		// do something
	}
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 24648 KB Correct: 498501 out of 500000 queries used.
2 Correct 115 ms 24656 KB Correct: 499500 out of 500000 queries used.
3 Correct 114 ms 24396 KB Correct: 492528 out of 500000 queries used.
4 Correct 110 ms 24524 KB Correct: 494515 out of 500000 queries used.
5 Correct 129 ms 24588 KB Correct: 498501 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 24648 KB Correct: 498501 out of 500000 queries used.
2 Correct 115 ms 24656 KB Correct: 499500 out of 500000 queries used.
3 Correct 114 ms 24396 KB Correct: 492528 out of 500000 queries used.
4 Correct 110 ms 24524 KB Correct: 494515 out of 500000 queries used.
5 Correct 129 ms 24588 KB Correct: 498501 out of 500000 queries used.
6 Correct 96 ms 24556 KB Correct: 495510 out of 500000 queries used.
7 Correct 101 ms 24628 KB Correct: 497503 out of 500000 queries used.
8 Correct 101 ms 24600 KB Correct: 497503 out of 500000 queries used.
9 Correct 114 ms 24556 KB Correct: 495510 out of 500000 queries used.
10 Correct 129 ms 24564 KB Correct: 496506 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Correct: 1980 out of 12000 queries used.
2 Correct 1 ms 468 KB Correct: 1984 out of 12000 queries used.
3 Correct 1 ms 468 KB Correct: 1998 out of 12000 queries used.
4 Correct 1 ms 468 KB Correct: 1984 out of 12000 queries used.
5 Correct 1 ms 468 KB Correct: 1980 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Correct: 1980 out of 12000 queries used.
2 Correct 1 ms 468 KB Correct: 1984 out of 12000 queries used.
3 Correct 1 ms 468 KB Correct: 1998 out of 12000 queries used.
4 Correct 1 ms 468 KB Correct: 1984 out of 12000 queries used.
5 Correct 1 ms 468 KB Correct: 1980 out of 12000 queries used.
6 Correct 1 ms 468 KB Correct: 1994 out of 12000 queries used.
7 Correct 2 ms 504 KB Correct: 1990 out of 12000 queries used.
8 Correct 1 ms 468 KB Correct: 1998 out of 12000 queries used.
9 Correct 1 ms 504 KB Correct: 1992 out of 12000 queries used.
10 Correct 1 ms 468 KB Correct: 1986 out of 12000 queries used.

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 24648 KB Correct: 498501 out of 500000 queries used.
2 Correct 115 ms 24656 KB Correct: 499500 out of 500000 queries used.
3 Correct 114 ms 24396 KB Correct: 492528 out of 500000 queries used.
4 Correct 110 ms 24524 KB Correct: 494515 out of 500000 queries used.
5 Correct 129 ms 24588 KB Correct: 498501 out of 500000 queries used.
6 Correct 96 ms 24556 KB Correct: 495510 out of 500000 queries used.
7 Correct 101 ms 24628 KB Correct: 497503 out of 500000 queries used.
8 Correct 101 ms 24600 KB Correct: 497503 out of 500000 queries used.
9 Correct 114 ms 24556 KB Correct: 495510 out of 500000 queries used.
10 Correct 129 ms 24564 KB Correct: 496506 out of 500000 queries used.
11 Correct 1 ms 468 KB Correct: 1980 out of 12000 queries used.
12 Correct 1 ms 468 KB Correct: 1984 out of 12000 queries used.
13 Correct 1 ms 468 KB Correct: 1998 out of 12000 queries used.
14 Correct 1 ms 468 KB Correct: 1984 out of 12000 queries used.
15 Correct 1 ms 468 KB Correct: 1980 out of 12000 queries used.
16 Correct 1 ms 468 KB Correct: 1994 out of 12000 queries used.
17 Correct 2 ms 504 KB Correct: 1990 out of 12000 queries used.
18 Correct 1 ms 468 KB Correct: 1998 out of 12000 queries used.
19 Correct 1 ms 504 KB Correct: 1992 out of 12000 queries used.
20 Correct 1 ms 468 KB Correct: 1986 out of 12000 queries used.
21 Incorrect 2 ms 468 KB Reported list of edges differ from actual.
22 Halted 0 ms 0 KB -