Submission #1184575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184575		lance0	Dreaming (IOI13_dreaming)	C++20	32 / 100	63 ms	15936 KiB

dreaming

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

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	vector<vector<vector<int>>> graph(N);
	for (int i = 0; i < M; i++) {
		int x,y,z; x = A[i]; y = B[i]; z = T[i];
		graph[x].push_back({y,z});
		graph[y].push_back({x,z});
	}
	vector<int> radius;
	vector<int> diameter;
	bool vis1[N] = {}, vis2[N] = {};
	int vis3[N] = {};
	for (int i = 0; i < N; i++) {
		if (!vis1[i]) {
			queue<pair<int, int>> bfs;
			bfs.push(make_pair(i, 0));
			vis1[i] = true;
			int start = 0, weight = 0;
			while (!bfs.empty()) {
				int x = bfs.front().first;
				int y = bfs.front().second;
				bfs.pop();
				if (y > weight) {
					start = x;
					weight = y;
				}
				for (int j = 0; j < graph[x].size(); j++) {
					if (vis1[graph[x][j][0]] == false) {
						bfs.push(make_pair(graph[x][j][0], graph[x][j][1]+y));
						vis1[graph[x][j][0]] = true;
					}
				}
			}
			bfs.push(make_pair(start, 0));
			vis2[start] = true;
			int end = 0; weight = 0;
			while (!bfs.empty()) {
				int x = bfs.front().first;
				int y = bfs.front().second;
				bfs.pop();
				if (y > weight) {
					end = x;
					weight = y;
				}
				for (int j = 0; j < graph[x].size(); j++) {
					if (vis2[graph[x][j][0]] == false) {
						bfs.push(make_pair(graph[x][j][0], graph[x][j][1]+y));
						vis2[graph[x][j][0]] = true;
					}
				}
			}
			diameter.push_back(weight);
			int rad = weight;
			stack<int> dfs;
			dfs.push(start);
			while (!dfs.empty()) {
				int x = dfs.top();
				if (x == end) {
					int curr = 0;
					dfs.pop();
					while (!dfs.empty()) {
						int y = dfs.top();
						dfs.pop();
						for (int j = 0; j < graph[x].size(); j++) {
							if (graph[x][j][0] == y) {
								curr += graph[x][j][1];
								rad = min(rad,max(curr,weight-curr));
								break;
							}
						}
						x = y;
					}
				} else if (vis3[x] == graph[x].size()) {
					dfs.pop();
				} else {
					dfs.push(graph[x][vis3[x]][0]);
					vis3[x]++;
				}
			}
			radius.push_back(rad);
		}
	}
	sort(radius.begin(), radius.end(), greater<int>());
	sort(diameter.begin(),diameter.end(), greater<int>());
	if (radius.size() == 1) {
		return (diameter[0]);
	} else if (radius.size() == 2) {
		return max({radius[0]+radius[1]+L, diameter[0]});
	} else {
		return max({radius[0]+radius[1]+L, radius[1]+radius[2]+L+L, diameter[0]});
	}
}

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