제출 #134812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134812		mirbek01	꿈 (IOI13_dreaming)	C++11	47 / 100	149 ms	24060 KiB

dreaming

#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;
			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 + len);
		} else {
			up[to] = max(up[to], vec[0].first + 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
**/

컴파일 시 표준 에러 (stderr) 메시지

dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:40:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(to == pr)
   ^~
dreaming.cpp:42:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    up[to] = max(up[to], up[v] + len);
    ^~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23