Submission #482214

#	Time	Username	Problem	Language	Result	Execution time	Memory
482214		M_W	Dreaming (IOI13_dreaming)	C++14	0 / 100	38 ms	7620 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define ii pair<int, int>
using namespace std;
vector<ii> adj[100001];
int pa[100001], from[100001], dist[100001];
bitset<100001> mark, mark2;

int findpa(int a){
	return (pa[a] == a ? a : pa[a] = findpa(pa[a]));
}

ii longestDist(int st){
	queue<ii> q;
	ii best = make_pair(-1, 0);
	q.push(make_pair(0, st));
	mark[st] = 1;
	while(!q.empty()){
		int d = q.front().first;
		int n = q.front().second;
		q.pop();
		
		if(d > best.first){
			best = make_pair(d, n);
		}
		
		for(auto x : adj[n]){
			if(!mark[x.first]){
				mark[x.first] = 1;
				q.push(make_pair(d + x.second, x.first));
			}
		}
	}
	q.push(make_pair(0, best.second));
	mark2[best.second] = 1;
	best = make_pair(-1, 0);
	while(!q.empty()){
		int d = q.front().first;
		int n = q.front().second;
		q.pop();
		
		dist[n] = d;
		if(d > best.first){
			best = make_pair(d, n);
		}
		
		for(auto x : adj[n]){
			if(!mark2[x.first]){
				from[x.first] = n;
				mark2[x.first] = 1;
				q.push(make_pair(d + x.second, x.first));
			}
		}
	}
	int mid = INT_MAX;
	for(int i = best.second; i != 0; i = from[i]){
		mid = min(mid, max(best.first - dist[i], dist[i]));
	}
	return make_pair(best.first, mid);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
	for(int i = 1; i <= N; i++) pa[i] = i;
	for(int i = 0; i < M; i++){
		A[i]++;
		B[i]++;
		adj[A[i]].emplace_back(B[i], T[i]);
		adj[B[i]].emplace_back(A[i], T[i]);
		if(findpa(A[i]) != findpa(B[i])){
			pa[findpa(B[i])] = findpa(A[i]);
		}
	}
	priority_queue<ii> pq;
	for(int i = 1; i <= N; i++){
		if(pa[i] == i){
			ii tmp = longestDist(i);
			pq.push(tmp);
			// printf(">> %d %d\n", tmp.first, tmp.second);
		}
	}
	if(pq.size() == 1) return 0;
	int cnt = 2, ans = 0;
	while(cnt--){
		ans += pq.top().second;
		pq.pop();
	}
	return ans + L;
}

/*
int main(){
	int a[8] = {0, 8, 2, 5, 5, 1, 1, 10}, b[8] = {8,2,7,11,1,3,9,6}, c[8] = {4,2,4,3,7,1,5,99};
	printf("%d", travelTime(12, 8, 2, a, b, c));
}
*/

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