oj.uz

답안 #586365

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

const int MAX_N = 1005;

int dist[MAX_N][MAX_N];
vector <pair <int, 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 furthest = 0, node = 1;
		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 <int, 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, prvDist = 0, M = 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 99 ms 12620 KB Correct: 498501 out of 500000 queries used.
2 Correct 107 ms 12572 KB Correct: 499500 out of 500000 queries used.
3 Correct 99 ms 12400 KB Correct: 492528 out of 500000 queries used.
4 Correct 89 ms 12432 KB Correct: 494515 out of 500000 queries used.
5 Correct 110 ms 12540 KB Correct: 498501 out of 500000 queries used.

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 12620 KB Correct: 498501 out of 500000 queries used.
2 Correct 107 ms 12572 KB Correct: 499500 out of 500000 queries used.
3 Correct 99 ms 12400 KB Correct: 492528 out of 500000 queries used.
4 Correct 89 ms 12432 KB Correct: 494515 out of 500000 queries used.
5 Correct 110 ms 12540 KB Correct: 498501 out of 500000 queries used.
6 Incorrect 97 ms 12616 KB Reported list of edges differ from actual.
7 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Correct: 1980 out of 12000 queries used.
2 Correct 2 ms 492 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 2 ms 468 KB Correct: 1980 out of 12000 queries used.

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Correct: 1980 out of 12000 queries used.
2 Correct 2 ms 492 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 2 ms 468 KB Correct: 1980 out of 12000 queries used.
6 Incorrect 1 ms 468 KB Reported list of edges differ from actual.
7 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 12620 KB Correct: 498501 out of 500000 queries used.
2 Correct 107 ms 12572 KB Correct: 499500 out of 500000 queries used.
3 Correct 99 ms 12400 KB Correct: 492528 out of 500000 queries used.
4 Correct 89 ms 12432 KB Correct: 494515 out of 500000 queries used.
5 Correct 110 ms 12540 KB Correct: 498501 out of 500000 queries used.
6 Incorrect 97 ms 12616 KB Reported list of edges differ from actual.
7 Halted 0 ms 0 KB -