Submission #703304

#	Time	Username	Problem	Language	Result	Execution time	Memory
703304		Doncho_Bonboncho	Dreaming (IOI13_dreaming)	C++14	100 / 100	493 ms	31732 KiB

dreaming

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

typedef long long ll;

const int MAX_N = 1e6 + 42;

std::vector<std::pair<int, int>> v[MAX_N];

int par[MAX_N];
int dist[MAX_N];

int center;
int d;

bool viz1[MAX_N];
bool viz[MAX_N];

void bfs( int x ){
	
//	std::cerr<<"\n\n";

	dist[x] = 0;
	center = x;
	d = 0;

	std::queue<std::pair<int, std::pair<int, int>>> q;
	q.push({x, {0, -2}});
	par[x] = x;

	while( q.size() ){
		auto curr = q.front();
		q.pop();
		int cur = curr.first;
		int currDist = curr.second.first;
		int currPar = curr.second.second;

//		std::cerr<<" # "<<cur<<" "<<currDist<<" "<<currPar<<"\n";

		par[cur] = currPar;
		viz[cur] = true;
		viz1[cur] = true;

		if( currDist > d ){
			d = currDist;
			center = cur;
		}
		for( auto j : v[cur] ){
			if( j.first == currPar or viz[j.first] ) continue;
			dist[j.first] = j.second;
			q.push({j.first, {currDist +  j.second, cur}});
		}
	}
}

std::vector<std::pair<int, int>> addEgd;

int travelTime(int n, int m, int l, int a[], int b[], int c[]) {

	for( int i=0 ; i<m ; i++ ){
		v[a[i]].push_back({b[i], c[i]});
		v[b[i]].push_back({a[i], c[i]});
	}

	/*
	for( int i=0 ; i<n ; i++ ){
		std::cerr<<i<<" : ";
		for( auto j : v[i] ) std::cerr<<j.first<<" "<<j.second<<" , ";
		std::cerr<<"\n";
	}
	*/

	for( int i=0 ; i<n ; i++ ){
		if( viz1[i] ) continue;
	//	std::cerr<<" ! "<<i<<"\n";
		for( int i=0 ; i<n ; i++ ) viz[i] = false;
		bfs( i );
		int x = center;
		for( int i=0 ; i<n ; i++ ) viz[i] = false;
		bfs( center );

	//	std::cerr<<center<<" "<<d<<"\n";

		if( d == 0 ){
			addEgd.push_back({0, i});
			continue;
		}

		int sum = 0;
		int curr = center;
		int p = -1;
		for( int j=0 ; j<n ; j++ ){
			sum += dist[curr];
			p = curr;
			curr = par[curr];
			if( sum * 2 > d ) break;
		}

		int a = std::max( sum, d-sum );
		sum -= dist[p];
		if( std::max( sum, d - sum ) < a ) addEgd.push_back({std::max(sum, d - sum), p});
		else addEgd.push_back({a, curr});
	//	std::cerr<<" $ "<<i<<" -> "<<addEgd[addEgd.size()-1].first<<" "<<addEgd[addEgd.size()-1].second<<"\n";
	}
	
	std::sort( addEgd.rbegin(), addEgd.rend() );

	int ind1 = addEgd[0].second;
	for( int i=1 ; i<addEgd.size() ; i++ ){
		int ind2 = addEgd[i].second;
		v[ind1].push_back({ind2, l});
		v[ind2].push_back({ind1, l});
	//	std::cerr<<" + "<<ind1<<" "<<ind2<<"\n";
	}
	for( int i=0 ; i<n ; i++ ) viz[i] = false;
	bfs(0);
	for( int i=0 ; i<n ; i++ ) viz[i] = false;
	bfs(center);
	int nas = d;
    return nas;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:78:7: warning: unused variable 'x' [-Wunused-variable]
   78 |   int x = center;
      |       ^
dreaming.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |  for( int i=1 ; i<addEgd.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