Submission #68123

#	Time	Username	Problem	Language	Result	Execution time	Memory
68123		thebes	Dreaming (IOI13_dreaming)	C++14	100 / 100	285 ms	24952 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 100005;
unordered_map<int,int> adj[SIZE]; pair<int,int> a[SIZE], b[SIZE], sol;
int u[SIZE], vis[SIZE]; vector<int> arr, vec;
bool comp1(int i, int j){return (max(a[i].first,u[i])>max(a[j].first,u[j]));}

int cmp1(int n, int p){
	unordered_map<int,int>::iterator it; vis[n] = 1;
	for(it=adj[n].begin();it!=adj[n].end();it++){
		if(it->first != p){
			pair<int,int> tmp = make_pair(cmp1(it->first,n)+it->second,it->first);
			if(tmp.first > a[n].first){b[n] = a[n]; a[n] = tmp;}
			else if(tmp.first > b[n].first){b[n] = tmp;}
		}
	}
	return a[n].first;
}

void cmp2(int n, int p){
	if(p != -1) u[n] = max(u[p],(a[p].second==n)?b[p].first:a[p].first)+adj[n][p];
	if(max(u[n],a[n].first)<sol.first) sol=make_pair(max(u[n],a[n].first),n);
	unordered_map<int,int>::iterator it;
	for(it=adj[n].begin();it!=adj[n].end();it++){if(it->first!=p) cmp2(it->first,n);}
}

int travelTime(int N, int M, int L, int *A, int *B, int *T){
	for(int i=0;i<M;i++) adj[A[i]][B[i]] = adj[B[i]][A[i]] = T[i];
	for(int i=0;i<N;i++){
		if(!vis[i]){
			sol.first = 1<<30; cmp1(i,-1); cmp2(i,-1);
			arr.push_back(sol.second);
		}
	}
	sort(arr.begin(), arr.end(), comp1);
	vec.push_back(u[arr[0]]); vec.push_back(a[arr[0]].first); vec.push_back(b[arr[0]].first);
	for(int i=1;i<(signed)arr.size()&&i<3;i++) vec.push_back(max(u[arr[i]],a[arr[i]].first)+L);
	sort(vec.begin(), vec.end(), greater<int>());
	return vec[0]+vec[1];
}

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