Submission #1288974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288974		muhammad-ahmad	Dreaming (IOI13_dreaming)	C++20	47 / 100	37 ms	9500 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

const int N = 1e5 + 5;
int vis[N], dist[N], par[N], MMM;
vector<pair<int, int>> adj[N];

int D(int u){
	dist[u] = 0;
	vector<int> C;
	queue<int> q;
	q.push(u);
	C.push_back(u);
	while (q.size()){
		int v = q.front(); q.pop();
		for (auto [i, w] : adj[v]){
			if (dist[i] > dist[v] + w){
				dist[i] = dist[v] + w;
				q.push(i);
				C.push_back(i);
			}
		}
	}
	
	int ma = N - 1;
	for (auto v : C){
		if (dist[v] > dist[ma]) ma = v;
		vis[v] = 1;
	}
	
	for (auto v : C){
		dist[v] = 1e9;
	}
	dist[ma] = 0;
	par[ma] = -1;
	q.push(ma);
	while (q.size()){
		int v = q.front(); q.pop();
		for (auto [i, w] : adj[v]){
			if (dist[i] > dist[v] + w){
				dist[i] = dist[v] + w;
				par[i] = v;
				q.push(i);
			}
		}
	}
	
	int ans = 1e9, M = N - 1;
	for (auto i : C){
		if (dist[i] > dist[M]) M = i;
		MMM = max(MMM, dist[i]);
	}
	
	int MM = M;
	
	// cout << ma << ' ' << MM  << endl;
	
	while (M != -1){
		ans = min(ans, max(dist[M], dist[MM] - dist[M]));
		M = par[M];
	}
	return ans;
	
}

int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
	for (int i = 0; i < N; i++) dist[i] = 1e9;
	dist[N - 1] = -15;
	for (int i = 0; i < m; i++){
		int u = A[i], v = B[i], w = T[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	
	vector<int> dim;
	
	for (int i = 0; i < n; i++){
		if (vis[i]) continue;
		dim.push_back(D(i));
	}
	
	sort(dim.rbegin(), dim.rend());
	if (dim.size() == 1){
		return MMM;
	}
	else {
		return max(MMM, dim[0] + dim[1] + l);
	}
	
	return 0;
}

// int main(){
	// int a[] = {0, 8, 2, 5, 5, 1, 1, 10};
	// int b[] = {8, 2, 7, 11, 1, 3, 9, 6};
	// int t[] = {4, 2, 4, 3, 7, 1, 5, 3};
	// cout << travelTime(12, 8, 2, a, b, t);
// }

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23