Submission #659033

#	Time	Username	Problem	Language	Result	Execution time	Memory
659033		angelo_torres	Dreaming (IOI13_dreaming)	C++17	100 / 100	89 ms	32532 KiB

dreaming

#include <bits/stdc++.h>
#include <dreaming.h>
 
using namespace std;
 
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
 
 
 
int n,m,l,a[100000],b[100000],t[100000];
int gp[100000],dp[100000];
bool vis[100000];
vii adj[100000];
vi gap,gru;
 
void dfs1(int v,int f){
	for(auto [u,w] : adj[v]){
		if(u == f) continue;
		dfs1(u,v);
		dp[v] = max(dp[u]+w,dp[v]); 
	}
}
 
void dfs2(int v,int f){
	gru.push_back(v);
	multiset<int> s;
	for(auto [u,w] : adj[v]){
		if(u == f) continue;
		s.insert(dp[u]+w);
	}
	for(auto [u,w] : adj[v]){
		if(u == f) continue;
		s.erase(s.find(dp[u]+w));
	
		int vl;
		if(!s.empty()){
			auto it = s.end(); it--;
			vl = *it;
		}
		else
			vl = 0;
		gp[u] = max(gp[v]+w,vl+w);
		s.insert(dp[u]+w);
	}
	for(auto [u,w] : adj[v]){
		if(u == f) continue;
		dfs2(u,v);
	}
}
 
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
	int ans = 0;
	n = N, m = M, l = L;
	for(int i = 0; i < m; ++i)
		a[i] = A[i], b[i] = B[i], t[i] = T[i];
	// cin >> n >> m >> l;
	// for(int i = 0; i < m; ++i) 
	// 	cin >> a[i] >> b[i] >> t[i];
	if(n == 1) return 0;
	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]});
	}
	for(int i = 0; i < n; ++i){
		if(vis[i])
			continue;
		dp[i] = 0, gp[i] = 0;
		dfs1(i,-1);
		dfs2(i,-1);
		int mn = dp[i]+gp[i];
		for(auto it : gru) 
			ans = max(dp[it]+gp[it],ans), mn = min(max(dp[it],gp[it]),mn), vis[it] = 1;
		// cout << i << endl;
		// for(auto it : gru){
		// 	cout << it << " " << dp[it] << " " << gp[it] << endl;
		// }
		// cout << mn << " d" << endl;
		gru.clear();
		gap.push_back(mn);
		// break;
	}
	sort(gap.rbegin(),gap.rend());
	if((int) gap.size() >= 2) ans = max(ans,gap[0]+gap[1]+l);
	if((int) gap.size() >= 3) ans = max(ans,gap[1]+gap[2]+l+l);
	return ans;
}
 
// int main(){
// 	int ldq1[2],ldq2[2],ldq3[3];
// 	cout << travelTime(0,0,0,ldq1,ldq2,ldq3) << endl;
// 	return 0;
// }

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