oj.uz

Submission #546798

# Submission time Handle Problem Language Result Execution time Memory
546798 2022-04-08T14:02:56 Z drkarlicio2107 Dreaming (IOI13_dreaming) C++14
18 / 100
 1000 ms 65536 KB 
// 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 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});
	}
	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);
		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());
	int ans=rad [0];
	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

dreaming.cpp: In function 'int dfs(int, 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: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:47: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]
   47 |   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);
      |       ^~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 12528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 12528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5700 KB Output is correct
2 Correct 21 ms 5716 KB Output is correct
3 Correct 19 ms 5716 KB Output is correct
4 Correct 23 ms 5716 KB Output is correct
5 Correct 21 ms 5716 KB Output is correct
6 Correct 26 ms 6148 KB Output is correct
7 Correct 24 ms 5804 KB Output is correct
8 Correct 30 ms 5652 KB Output is correct
9 Correct 22 ms 5588 KB Output is correct
10 Correct 18 ms 5836 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 4 ms 3664 KB Output is correct
13 Correct 5 ms 3648 KB Output is correct
14 Correct 4 ms 3664 KB Output is correct
15 Correct 4 ms 3664 KB Output is correct
16 Correct 4 ms 3664 KB Output is correct
17 Correct 4 ms 3536 KB Output is correct
18 Correct 5 ms 3744 KB Output is correct
19 Correct 5 ms 3664 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 5 ms 3664 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 12528 KB Time limit exceeded
2 Halted 0 ms 0 KB -