Submission #476526

#	Time	Username	Problem	Language	Result	Execution time	Memory
476526		dsyz	Dreaming (IOI13_dreaming)	C++14	100 / 100	211 ms	19928 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long;
#define MAXN (100005)
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	vector<pair<ll,ll> > v[N];
	for(ll i = 0;i < M;i++){
		ll a,b,c;
		a = A[i];
		b = B[i];
		c = T[i];
		v[a].push_back(make_pair(b,c));
		v[b].push_back(make_pair(a,c));
	}
	vector<pair<ll,ll> > ans;
	vector<ll> component[N];
	queue<ll> q;
	ll dist[N];
	ll dist2[N];
	ll dist3[N];
	ll dist4[N];
	int visited[N];
	int visited2[N];
	int visited3[N];
	int visited4[N];
	memset(dist,0,sizeof(dist));
	memset(visited,0,sizeof(visited));
	memset(dist2,0,sizeof(dist2));
	memset(visited2,0,sizeof(visited2));
	memset(dist3,0,sizeof(dist3));
	memset(visited3,0,sizeof(visited3));
	memset(dist4,0,sizeof(dist4));
	memset(visited4,0,sizeof(visited4));
	for(ll i = 0;i < N;i++){
		if(visited[i] != 0){
			continue;
		}
		q.push(i);
		dist[i] = 0;
		component[i].push_back(i);
		visited[i] = 1;
		while(!q.empty()){
			ll a = q.front();
			q.pop();
			visited[a] = 1;
			for(auto u : v[a]){
				if(visited[u.first] == 0 || dist[a] + u.second < dist[u.first]){
					if(visited[u.first] == 0){
						component[i].push_back(u.first);
					}
					q.push(u.first);
					dist[u.first] = dist[a] + u.second;
					visited[u.first] = 1;
				}
			}
		}
		ll index = 0;
		ll num = 0;
		for(ll j = 0;j < component[i].size();j++){
		    ll a = component[i][j];
			if(dist[a] > num){
				num = dist[a];
				index = a;
			}
		}
		q.push(index);
		dist2[index] = 0;
		visited2[index] = 1;
		ll sum = 0;
		while(!q.empty()){
			ll a = q.front();
			q.pop();
			visited2[a] = 1;
			for(auto u : v[a]){
				if(visited2[u.first] == 0 || dist2[a] + u.second < dist2[u.first]){
					q.push(u.first);
					dist2[u.first] = dist2[a] + u.second;
					visited2[u.first] = 1;
				}
			}
		}
		ll index2 = 0;
		for(ll j = 0;j < component[i].size();j++){
		    ll a = component[i][j];
			if(dist2[a] > sum){
				index2 = a;
				sum = dist2[a];
			}
		}
		q.push(index);
		dist3[index] = 0;
		visited3[index] = 1;
		while(!q.empty()){
			ll a = q.front();
			q.pop();
			visited3[a] = 1;
			for(auto u : v[a]){
				if(visited3[u.first] == 0 || dist3[a] + u.second < dist3[u.first]){
					q.push(u.first);
					dist3[u.first] = dist3[a] + u.second;
					visited3[u.first] = 1;
				}
			}
		}
		q.push(index2);
		dist4[index2] = 0;
		visited4[index2] = 1;
		while(!q.empty()){
			ll a = q.front();
			q.pop();
			visited4[a] = 1;
			for(auto u : v[a]){
				if(visited4[u.first] == 0 || dist4[a] + u.second < dist4[u.first]){
					q.push(u.first);
					dist4[u.first] = dist4[a] + u.second;
					visited4[u.first] = 1;
				}
			}
		}
		pair<ll,ll> maximum = make_pair(-1,0);
		for(ll j = 0;j < component[i].size();j++){
			ll a = component[i][j];
			if(maximum.first == -1 || max(dist3[a],dist4[a]) < maximum.first){
				maximum.first = max(dist3[a],dist4[a]);
				maximum.second = a;
			}
		}
		ans.push_back(make_pair(maximum.first,maximum.second));
	}
	sort(ans.begin(),ans.end(),greater<pair<ll,ll> >());
	for(ll i = 1;i < ans.size();i++){
		ll a = ans[0].second;
		ll b = ans[i].second;
		v[a].push_back(make_pair(b,L));
		v[b].push_back(make_pair(a,L));
	}
	memset(dist,0,sizeof(dist));
	memset(visited,0,sizeof(visited));
	memset(dist2,0,sizeof(dist2));
	memset(visited2,0,sizeof(visited2));
	q.push(0);
	dist[0] = 0;
	visited[0] = 1;
	while(!q.empty()){
		ll a = q.front();
		q.pop();
		visited[a] = 1;
		for(auto u : v[a]){
			if(visited[u.first] == 0 || dist[a] + u.second < dist[u.first]){
				q.push(u.first);
				dist[u.first] = dist[a] + u.second;
				visited[u.first] = 1;
			}
		}
	}
	ll index = 0;
	ll num = 0;
	for(ll i = 0;i < N;i++){
		if(dist[i] > num){
			num = dist[i];
			index = i;
		}
	}
	q.push(index);
	dist2[index] = 0;
	visited2[index] = 1;
	ll sum = 0;
	while(!q.empty()){
		ll a = q.front();
		q.pop();
		visited2[a] = 1;
		for(auto u : v[a]){
			if(visited2[u.first] == 0 || dist2[a] + u.second < dist2[u.first]){
				q.push(u.first);
				dist2[u.first] = dist2[a] + u.second;
				visited2[u.first] = 1;
			}
		}
	}
	for(ll i = 0;i < N;i++){
		if(dist2[i] > sum){
			sum = dist2[i];
		}
	}
	return sum;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:60:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(ll j = 0;j < component[i].size();j++){
      |                ~~^~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:84:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for(ll j = 0;j < component[i].size();j++){
      |                ~~^~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:122:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   for(ll j = 0;j < component[i].size();j++){
      |                ~~^~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:132:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |  for(ll i = 1;i < ans.size();i++){
      |               ~~^~~~~~~~~~~~

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