oj.uz

Submission #134803

# Submission time Handle Problem Language Result Execution time Memory
134803 2019-07-23T09:35:05 Z mirbek01 Dreaming (IOI13_dreaming) C++11
0 / 100
 77 ms 15224 KB 
#include "dreaming.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 3;

int u[N], dw[N], up[N], ans, mx;
vector < pair <int, int> >  g[N];

void dfs(int v, int pr){
	u[v] = 1;
	int mx1 = 0, mx2 = 0;
	for(int i = 0; i < (int)g[v].size(); i ++){
		int to = g[v][i].first, len = g[v][i].second;
		if(to == pr)
			continue;
		dfs(to, v);
		dw[v] = max(dw[v], dw[to] + len); 
		if(mx1 < dw[to] + len)
			mx2 = mx1, mx1 = dw[to] + len;
		else 
			mx2 = max(mx2, dw[to] + len);
	} 
	ans = max(ans, mx1 + mx2);
}
	
void dfs1(int v, int pr){
	mx = min(mx, max(up[v], dw[v]));
	vector < pair <int, int> > vec;
	for(int i = 0; i < (int)g[v].size(); i ++){
		int to = g[v][i].first, len = g[v][i].second;
		if(to == pr) continue;
		vec.push_back( {dw[to] + len, to} );
	}
	sort(vec.rbegin(), vec.rend());
	for(int i = 0; i < (int)g[v].size(); i ++){
		int to = g[v][i].first, len = g[v][i].second;
		if(to == pr)
			continue;
		if(to == vec[0].second){
			if((int)vec.size() > 1)
				up[to] = max(up[to], vec[1].first + len), 
				up[to] = max(up[to], up[v] + len);	
		} else {
			up[to] = max(up[to], vec[0].first + len),
			up[to] = max(up[to], up[v] + len);
		}
		dfs1(to, v);
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for(int i = 0; i < M; i ++){
		int u = A[i], v = B[i], w = T[i];
		g[u].push_back( {v, w} );
		g[v].push_back( {u, w} );
	}

	vector <int> vec;
	
	for(int i = 0; i < N; i ++){
		if(!u[i]){
			mx = 2e9;
			dfs(i, -1);
			dfs1(i, -1);
			vec.push_back(mx);
		}
	}
	
	sort(vec.rbegin(), vec.rend());
	
	if((int)vec.size() > 1)
		ans = max(ans, vec[0] + vec[1] + L);
		
	return ans;
}
/**
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
**/

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 15224 KB Output is correct
2 Correct 75 ms 14584 KB Output is correct
3 Correct 56 ms 13688 KB Output is correct
4 Correct 14 ms 4472 KB Output is correct
5 Correct 12 ms 3708 KB Output is correct
6 Correct 22 ms 5496 KB Output is correct
7 Incorrect 4 ms 2808 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 15224 KB Output is correct
2 Correct 75 ms 14584 KB Output is correct
3 Correct 56 ms 13688 KB Output is correct
4 Correct 14 ms 4472 KB Output is correct
5 Correct 12 ms 3708 KB Output is correct
6 Correct 22 ms 5496 KB Output is correct
7 Incorrect 4 ms 2808 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 15224 KB Output is correct
2 Correct 75 ms 14584 KB Output is correct
3 Correct 56 ms 13688 KB Output is correct
4 Correct 14 ms 4472 KB Output is correct
5 Correct 12 ms 3708 KB Output is correct
6 Correct 22 ms 5496 KB Output is correct
7 Incorrect 4 ms 2808 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 6096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 15224 KB Output is correct
2 Correct 75 ms 14584 KB Output is correct
3 Correct 56 ms 13688 KB Output is correct
4 Correct 14 ms 4472 KB Output is correct
5 Correct 12 ms 3708 KB Output is correct
6 Correct 22 ms 5496 KB Output is correct
7 Incorrect 4 ms 2808 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 15224 KB Output is correct
2 Correct 75 ms 14584 KB Output is correct
3 Correct 56 ms 13688 KB Output is correct
4 Correct 14 ms 4472 KB Output is correct
5 Correct 12 ms 3708 KB Output is correct
6 Correct 22 ms 5496 KB Output is correct
7 Incorrect 4 ms 2808 KB Output isn't correct
8 Halted 0 ms 0 KB -