Submission #482424

#	Time	Username	Problem	Language	Result	Execution time	Memory
482424		M_W	Dreaming (IOI13_dreaming)	C++14	100 / 100	76 ms	8992 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(mid, best.first);
}

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]);
		}
	}
	int aaa = 0;
	priority_queue<ii> pq;
	for(int i = 1; i <= N; i++){
		if(pa[i] == i){
			ii tmp = longestDist(i);
			pq.push(tmp);
			aaa = max(aaa, tmp.second);
		}
	}
	if(pq.size() == 1) return aaa;
	int ans = 0;
	int aaa2 = 0;
	if(pq.size() > 2){
		for(int i = 1; i <= 3; i++){
			if(i <= 2) ans += pq.top().first;
			if(i > 1 && i <= 3) aaa2 += pq.top().first;
			pq.pop();
		}	
		return max(aaa, max(ans + L, aaa2 + L + L));
	}
	else{
		for(int i = 1; i < 3; i++){
			ans += pq.top().first;
			pq.pop();
		}
		return max(aaa, ans + L);	
	}	
}

/*
int main(){
	int N, M, L;
	scanf("%d %d %d", &N, &M, &L);
	int a[M], b[M], c[M];
	for(int i = 0; i < M; i++){
		scanf("%d %d %d", &a[i], &b[i], &c[i]);
	}
	printf("%d", travelTime(N, M, L, a, b, c));
}
*/

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