Submission #546783

#	Time	Username	Problem	Language	Result	Execution time	Memory
546783		drkarlicio2107	꿈 (IOI13_dreaming)	C++14	Compilation error	0 ms	0 KiB

dreaming

// code by: Karlo Brcic
// Dreaming, IOI 2013
#include <bits/stdc++.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;
int dfs (int x, int par, int zapis, 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;
		if (ans<dfs (y, x, zapis, tre+g[x][i].second)+g[x][i].second){
			ans=dfs (y, x, zapis, tre+g[x][i].second)+g[x][i].second;
			tko=y; dulj=g[x][i].second;
		}
	}
	if (tko!=-1 && zapis){
		red.push_back ({tko, dulj});
	}
	//cout << x << " " << ans << endl;
	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=-1;
	for (int i=0; i<N; i++){
		if (bio [i]) continue;
		red.clear();
		maxi=-1;
		int fur1=dfs (i, -1, 0, 0);
		maxi=-1;
		int fur2=dfs (maxi2, -1, 1, 0);
		ans=max (ans, fur2);
		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);
		//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, int)':
dreaming.cpp:15: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]
   15 |  for (int i=0; i<g[x].size(); i++){
      |                ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:48: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]
   48 |   for (int j=0; j<red.size(); j++){
      |                 ~^~~~~~~~~~~
dreaming.cpp:42:7: warning: unused variable 'fur1' [-Wunused-variable]
   42 |   int fur1=dfs (i, -1, 0, 0);
      |       ^~~~
/usr/bin/ld: /tmp/ccbAujTx.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status