Submission #546820

#	Time	Username	Problem	Language	Result	Execution time	Memory
546820		drkarlicio2107	Dreaming (IOI13_dreaming)	C++14	18 / 100	142 ms	65536 KiB

dreaming

// code by: Karlo Brcic
// Dreaming, IOI 2013
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std; 
//int A [100010], B [100010], T [100010];
vector < pair <int, int> > g [100010];
int bio [100010];
vector <int> rad; vector < pair <int, int> > red;
int maxi=-1, maxi2=0;
int dfs (int x, int par, int tre){ // returns the furtherest point from x
	int ans=0; bio [x]=1; int tko=-1; int dulj=-1;
	if (tre>maxi){
		maxi=tre; maxi2=x;
	}
	for (int i=0; i<g[x].size(); i++){
		int y=g[x][i].first;
		if (y==par) continue;
		int b=dfs (y, x, tre+g[x][i].second)+g[x][i].second;
		if (ans<b){
			ans=b;
			tko=y; dulj=g[x][i].second;
		}
	}
	return ans;
}
int rec (int x, int par, int trazi){ //reconstruct
	int ans=0; int dulj;
	for (int i=0; i<g[x].size(); i++){
		int y=g[x][i].first;
		if (y==par) continue;
		if (rec (y, x, trazi)>ans){
			ans=rec (y, x, trazi); dulj=g[x][i].second;
		}
	}
	if (x==trazi) ans=1;
	if (ans==1){
		red.push_back ({x, dulj});
	}
	return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
	for (int i=0; i<M; i++){
		int a=A [i];
		int b=B [i];
		int c=T [i];
		g [a].push_back ({b, c});
		g [b].push_back ({a, c});
	}
	int ans=0;
	for (int i=0; i<N; i++){
		if (bio [i]) continue;
		red.clear();
		maxi=-1;
		int fur1=dfs (i, -1, 0);
		maxi=-1; int poc=maxi2;
		int fur2=dfs (poc, -1, 0);
		rec (poc, -1, maxi2);
		reverse (red.begin(), red.end());
		int tre=0; int r=fur2;
		for (int j=0; j<red.size(); j++){
			tre+=red[j].second;
			r=min (r, max (tre, fur2-tre));
		}
		rad.push_back (r);
		ans=max (ans, fur2);
		//cout << fur2 << endl;
	}
	sort (rad.rbegin(), rad.rend());
	if (rad.size()>=2){
		ans=max (ans, rad [0]+rad[1]+L);
	}
	if (rad.size()>=3){
		ans=max (ans, rad [1]+rad[2]+2*L);
	}
	return ans;
}
/*int main (){
	int n, m, l; cin >> n >> m >> l;
	for (int i=0; i<m; i++) cin >> A [i] >> B [i] >> T [i];
	cout << travelTime (n, m, l, A, B, T);
	return 0;
}*/

Compilation message (stderr)

dreaming.cpp: In function 'int dfs(int, int, int)':
dreaming.cpp:16:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for (int i=0; i<g[x].size(); i++){
      |                ~^~~~~~~~~~~~
dreaming.cpp:12:28: warning: variable 'tko' set but not used [-Wunused-but-set-variable]
   12 |  int ans=0; bio [x]=1; int tko=-1; int dulj=-1;
      |                            ^~~
dreaming.cpp:12:40: warning: variable 'dulj' set but not used [-Wunused-but-set-variable]
   12 |  int ans=0; bio [x]=1; int tko=-1; int dulj=-1;
      |                                        ^~~~
dreaming.cpp: In function 'int rec(int, int, int)':
dreaming.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for (int i=0; i<g[x].size(); i++){
      |                ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for (int j=0; j<red.size(); j++){
      |                 ~^~~~~~~~~~~
dreaming.cpp:55:7: warning: unused variable 'fur1' [-Wunused-variable]
   55 |   int fur1=dfs (i, -1, 0);
      |       ^~~~

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