Submission #586749

#	Time	Username	Problem	Language	Result	Execution time	Memory
586749		AlperenT	Dreaming (IOI13_dreaming)	C++17	47 / 100	90 ms	15660 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

const int N = 1e5 + 5, INF = 1e9 + 5;

int n, m, l, maxdia, ans = INF, dist1[N], dist2[N];

vector<pair<int, int>> tree[N];

vector<int> sets, nodes;

bool vis[N];

pair<int, int> dfs(int v, int p){
	nodes.push_back(v);

	pair<int, int> mx = {0, v};

	for(auto e : tree[v]){
		if(e.first != p){
			pair<int, int> emx = dfs(e.first, v);

			mx = max(mx, {emx.first + e.second, emx.second});
		}
	}

	return mx;
}

void dfs2(int v, int p, int d, int* dist){
	dist[v] = d;

	for(auto e : tree[v]){
		if(e.first != p){
			dfs2(e.first, v, d + e.second, dist);
		}
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
	n = N, m = M, l = L;

	for(int i = 0; i < m; i++){
		tree[A[i]].push_back({B[i], T[i]});
		tree[B[i]].push_back({A[i], T[i]});
	}

	for(int v = 0; v < n; v++){
		nodes.clear();

		if(!vis[v]){
			auto p1 = dfs(v, -1);

			int a = p1.second;

			auto p2 = dfs(a, -1);

			int b = p2.second;

			maxdia = max(maxdia, p2.first);

			auto p3 = dfs(b, -1);

			dfs2(a, -1, 0, dist1);
			dfs2(b, -1, 0, dist2);

			int mx = INF;

			for(auto u : nodes) mx = min(mx, max(dist1[u], dist2[u])), vis[u] = true;

			sets.push_back(mx);
		}
	}

	multiset<int> st;

	for(auto x : sets) st.insert(x);
	
	for(auto x : sets){
		st.erase(st.find(x));

		int curans = 0;

		if(st.size() == 0) curans = INF;
		if(st.size() >= 1) curans = max(curans, x + *prev(st.end()) + l);
		if(st.size() >= 2) curans = max(curans, *prev(st.end()) + *prev(prev(st.end())) + 2 * l);

		ans = min(ans, curans);

		st.insert(x);
	}

    return max(ans, maxdia);
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:64:9: warning: variable 'p3' set but not used [-Wunused-but-set-variable]
   64 |    auto p3 = dfs(b, -1);
      |         ^~

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