Submission #545297

#	Time	Username	Problem	Language	Result	Execution time	Memory
545297		benson1029	Dreaming (IOI13_dreaming)	C++14	100 / 100	104 ms	15912 KiB

dreaming

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

vector< pair<int,int> > edg[100005];
int vis[100005];
int bck[100005], dis[100005];
int mxdis = -1, mxdisnode = 0;
vector<int> v;

void dfs(int x, int p, int d) {
	vis[x] = 1;
	if(d>mxdis) {
		mxdis = d; mxdisnode = x;
	}
	for(auto i:edg[x]) {
		if(i.first!=p) {
			bck[i.first] = x;
			dis[i.first] = i.second;
			dfs(i.first, x, d+i.second);
		}
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i=0; i<M; i++) {
    	edg[A[i]].push_back({B[i],T[i]});
    	edg[B[i]].push_back({A[i],T[i]});
	}
	int ans = 0;
	for(int i=0; i<N; i++) {
		if(vis[i]==0) {
			mxdis = -1;
			dfs(i, -1, 0);
			mxdis = -1;
			int orig = mxdisnode;
			dfs(orig, -1, 0);
			int ptr = mxdisnode;
			int cendis = mxdis, cnt = 0;
			while(ptr != orig) {
				cnt += dis[ptr]; 
				ptr = bck[ptr];
				if(max(cnt, mxdis - cnt) < cendis) {
					cendis = max(cnt, mxdis - cnt);
				}
			}
			ans = max(ans, mxdis);
			v.push_back(cendis);
		}
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	if(v.size() >= 2) {
		ans = max(ans, v[0] + v[1] + L);
	}
	if(v.size() >= 3) {
		ans = max(ans, v[1] + v[2] + L*2);
	}
	return ans;
}

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