oj.uz

Submission #546820

# Submission time Handle Problem Language Result Execution time Memory
546820 2022-04-08T14:35:02 Z drkarlicio2107 Dreaming (IOI13_dreaming) C++14
18 / 100
 142 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 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

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.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 109 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 Runtime error 142 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5720 KB Output is correct
2 Correct 19 ms 5724 KB Output is correct
3 Correct 22 ms 5720 KB Output is correct
4 Correct 23 ms 5696 KB Output is correct
5 Correct 32 ms 5676 KB Output is correct
6 Correct 29 ms 6052 KB Output is correct
7 Correct 19 ms 5844 KB Output is correct
8 Correct 18 ms 5592 KB Output is correct
9 Correct 20 ms 5676 KB Output is correct
10 Correct 19 ms 5844 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 6 ms 3664 KB Output is correct
13 Correct 6 ms 3664 KB Output is correct
14 Correct 6 ms 3628 KB Output is correct
15 Correct 7 ms 3664 KB Output is correct
16 Correct 8 ms 3664 KB Output is correct
17 Correct 8 ms 3536 KB Output is correct
18 Correct 7 ms 3664 KB Output is correct
19 Correct 8 ms 3664 KB Output is correct
20 Correct 1 ms 2644 KB Output is correct
21 Correct 1 ms 2644 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 6 ms 3664 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 109 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 Runtime error 142 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -