oj.uz

답안 #421645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
421645 2021-06-09T10:25:36 Z SuhaibSawalha1 꿈 (IOI13_dreaming) C++17
0 / 100
 64 ms 9024 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<array<int, 2>>> adj;
vector<int> dist, nodes;
int n;

int bfs (int u, bool f) {
	queue<array<int, 3>> q {{{u, 0}}};
	array<int, 2> MX {0, u};
	int v = 0;
	while (q.size()) {
		++v;
		u = q.front()[0];
		int d = q.front()[1];
		int p = q.front()[2];
		q.pop();
		if (f) {
			nodes.push_back(u);
			dist[u] = max(dist[u], d);
		}
		MX = max(MX, {d, u});
		for (auto &v : adj[u]) {
			if (v[0] != p) {
				q.push({v[0], d + v[1], u});
			}
		}
	}
	return MX[1];
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n = N;
	adj.resize(N);
	dist.resize(N);
	for (int i = 0; i < M; ++i) {
		adj[A[i]].push_back({B[i], T[i]});
		adj[B[i]].push_back({A[i], T[i]});
	}
	vector<int> cmp;
	for (int i = 0; i < N; ++i) {
		if (!dist[i]) {
			int a = bfs(i, 0);
			nodes.clear();
			bfs(bfs(a, 1), 1);
			int mn = 2e9;
			for (int u : nodes) {
				mn = min(mn, dist[u]);
			}
			cmp.push_back(mn);
		}
	}
	sort(cmp.begin(), cmp.end());
	return cmp.size() == 1 ? cmp[0] : cmp[cmp.size() - 2] + cmp.back() + L;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 9024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 9024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 5948 KB Output is correct
2 Incorrect 53 ms 5992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 9024 KB Output isn't correct
2 Halted 0 ms 0 KB -