제출 #319629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
319629		miss_robot	Dreaming (IOI13_dreaming)	C++14	100 / 100	152 ms	27492 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

#pragma GCC optimize("O3")

using namespace std;

int n, m, l;
vector< vector< pair<int, int> > > g;
vector<int> maxk;

void furthest(int u, int p, int &f, int &d, int s){
	if(s > d) d = s, f = u;
	for(auto &t : g[u]){
		if(t.first == p) continue;
		furthest(t.first, u, f, d, s+t.second);
	}
}

void dfs(int u, int p){
	maxk[u] = 0;
	for(auto &t : g[u]){
		if(t.first == p) continue;
		dfs(t.first, u);
		maxk[u] = max(maxk[u], maxk[t.first]+t.second);
	}
}

void dfs2(int u, int p, int o, int &f, int &d){
	if(max(o, maxk[u]) < d) d = max(o, maxk[u]), f = u;
	vector<int> r;
	for(auto &t : g[u]){
		if(t.first == p) continue;
		r.push_back(t.second+maxk[t.first]);
	}
	sort(r.rbegin(), r.rend());
	for(auto &t : g[u]){
		if(t.first == p) continue;
		int temp = o+t.second;
		if(maxk[t.first]+t.second != r[0]) temp = max(temp, r[0]+t.second);
		else if(r.size() > 1) temp = max(temp, r[1]+t.second);
		dfs2(t.first, u, temp, f, d);
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
	n = N, m = M, l = L;
	g.resize(n);
	for(int i = 0; i < m; i++){
		g[A[i]].push_back({B[i], T[i]});
		g[B[i]].push_back({A[i], T[i]});
	}
	vector< pair<int, int> > r;
	maxk.assign(n, -1);
	for(int i = 0; i < n; i++) if(maxk[i] == -1){
		dfs(i, -1);
		int f, d = 1e9;
		dfs2(i, -1, 0, f, d);
		r.push_back({d, f});
	}
	sort(r.rbegin(), r.rend());
	for(int i = 1; i < (int)r.size(); i++){
		g[r[0].second].push_back({r[i].second, l});
		g[r[i].second].push_back({r[0].second, l});
	}
	int f, d = -1;
	furthest(0, -1, f, d, 0);
	d = -1;
	furthest(f, -1, f, d, 0);
	return d;
}

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