oj.uz

답안 #134780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
134780 2019-07-23T09:15:07 Z mirbek01 꿈 (IOI13_dreaming) C++11
0 / 100
 92 ms 16792 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){
	ans = max(ans, up[v] + dw[v]);
	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;
		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;
		up[to] = max(up[to], up[v] + len);
		if(to == vec[0].second){
			if((int)vec.size() > 1)
				up[to] = max(up[to], vec[1].first);	
		} else {
			up[to] = max(up[to], vec[0].first);
		}
		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;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 92 ms 16792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 92 ms 16792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 92 ms 16792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 6904 KB Output is correct
2 Incorrect 38 ms 6932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 92 ms 16792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 92 ms 16792 KB Output isn't correct
2 Halted 0 ms 0 KB -