Submission #1023938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023938		berr	Dreaming (IOI13_dreaming)	C++17	100 / 100	64 ms	23296 KiB

dreaming

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

///#define int long long


void f(){
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
   vector<vector<array<int, 2>>> g(n);

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

	vector<int> vis(n), ma(n);
	int ans=0, sum, mi;
	vector<int> all;
	auto dfs=[&](int v, int p, auto&&dfs)->void{
		vis[v]=1;
		vector<int> x;
		for(auto [i, c]: g[v]){
			if(i==p) continue;
			dfs(i, v,  dfs);
			ma[v]=max(ma[v], ma[i]+c);
			x.push_back(ma[i]+c);
		}
	
		sort(x.begin(), x.end(), [&](int a, int b){
			return a>b;
		});

		if(x.size()==1){
			if(sum<x[0]){
				sum=x[0];
				mi=x[0];
			}
			else if(sum==x[0]){
				mi=min(mi,x[0]);
			}
		}
		else if(x.size()>1){
			if(sum<x[0]+x[1]){
				sum=x[0]+x[1];
				mi=x[0];
			}
			else if(sum==x[0]+x[1]){
				mi=min(mi,x[0]);
			}
		}
	};

	auto dfs2=[&](int v, int p, auto&&dfs2)->void{
		int maa=0, id=0;
		int tmp=ma[v];
		for(auto [i, c]: g[v]){
			if(ma[i]+c>maa) maa=ma[i]+c, id=i;
		}

		int maa2=0, id2=0;
		for(auto [i, c]: g[v]){
			if(ma[i]+c>maa2&&i!=id) maa2=ma[i]+c, id2=i;
		}

		if(g[v].size()==1&&p!=v) return;
		for(auto [i, c]: g[v]){
			if(i!=p&&id!=i){
				ma[v]=maa;

				dfs2(i, v, dfs2);
				ma[v]=tmp;
			}
			else if(i==id&&i!=p){
				ma[v]=maa2;

				dfs2(i, v, dfs2);
			}
		}
		if(maa+maa2==sum){
			mi=min(mi, maa);
		}
		ma[v]=tmp;
	};

	for(int i=0; i<n; i++){
		if(vis[i]) continue;
		mi=1e18, sum=0;

		dfs(i, i, dfs);
		dfs2(i, i, dfs2);
		ans=max(ans, sum);
		all.push_back(mi);
	}

	sort(all.begin(), all.end(), [&](int a, int b){
		return a>b;
	});
	if(all.size()>1) ans=max(ans, all[0]+all[1]+L);
	if(all.size()>2) ans=max(ans, all[1]+all[2]+2*L);
	return ans;
}/*
signed main(){
	f();
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m, L; cin >> n >> m >> L;

	
}	*/

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:95:6: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   95 |   mi=1e18, sum=0;
      |      ^~~~
dreaming.cpp: In instantiation of 'travelTime(int, int, int, int*, int*, int*)::<lambda(int, int, auto:24&&)> [with auto:24 = travelTime(int, int, int, int*, int*, int*)::<lambda(int, int, auto:24&&)>&]':
dreaming.cpp:98:18:   required from here
dreaming.cpp:68:15: warning: variable 'id2' set but not used [-Wunused-but-set-variable]
   68 |   int maa2=0, id2=0;
      |               ^~~
dreaming.cpp: In function 'void f()':
dreaming.cpp:10:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  freopen("in.txt", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:11:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  freopen("out.txt", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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