Submission #58759

#	Time	Username	Problem	Language	Result	Execution time	Memory
58759		Sherazin	Dreaming (IOI13_dreaming)	C++14	100 / 100	111 ms	16760 KiB

dreaming

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

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e5 + 5;

vector<vector<pii> > g(N);
pii dp[N];
bitset<N> vis;
vector<int> center;
int dm;

pii dfs1(int u, int p, int d) {
	vis[u] = 1;
	dp[u] = pii(p, d);
	pii ret = {d, u};
	for(pii v : g[u]) if(v.x != p) ret = max(ret, dfs1(v.x, u, d + v.y));
	return ret;
}

bool comp(const int &a, const int &b) {
	return a > b;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 0; i < M; i++) {
    	g[A[i]].emplace_back(B[i], T[i]);
    	g[B[i]].emplace_back(A[i], T[i]);
    }

    for(int i = 0; i < N; i++) if(!vis[i]) {
    	vector<pii> path;
    	int root = dfs1(i, i, 0).y;
    	pii leaf = dfs1(root, root, 0);

    	int now = leaf.y;
    	int diameter = leaf.x;
    	dm = max(dm, diameter);

    	if(M == N - 1) return diameter;

    	while(dp[now].x != now) {
    		path.emplace_back(now, dp[now].y);
    		now = dp[now].x;
    	}
    	path.emplace_back(root, 0);
    	int mxd = INT_MAX;
    	for(pii node : path) if(max(node.y, diameter - node.y) < mxd) mxd = max(node.y, diameter - node.y);
    	center.emplace_back(mxd);
    }

    sort(center.begin(), center.end(), comp);
    if(center.size() == 2) return max(center[0] + center[1] + L, dm);
    else return max(dm, max(center[0] + center[1] + L, center[1] + center[2] + 2*L));
}

/*int main() {
	int n, m, l;
	scanf("%d%d%d", &n, &m, &l);
	int a[m], b[m], t[m];
	for(int i = 0; i < m; i++) {
		scanf("%d%d%d", &a[i], &b[i], &t[i]);
	} 

	printf("%d", travelTime(n, m, l, a, b, t));

	return 0;
}*/

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