Submission #18010

#	Time	Username	Problem	Language	Result	Execution time	Memory
18010		suhgyuho_william	Dreaming (IOI13_dreaming)	C++98	100 / 100	103 ms	9116 KiB

dreaming

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N,M,L;
int a[100002];
int d[100002],q[100002];
int dia[100002],tmp;
int path[100002];
bool check[100002];
vector<pair<int,int> > edge[100002];

int bfs(int x){
	int i,r;
	int v,nextv,big;
	int top,rear,ansv;

	top = 0;
	rear = 1;
	q[1] = x;
	d[x] = 0;
	while(true){
		top++;
		if(top > rear) break;
		for(i=0; i<edge[q[top]].size(); i++){
			v = edge[q[top]][i].first;
			if(d[v] > d[q[top]]+edge[q[top]][i].second){
				d[v] = d[q[top]]+edge[q[top]][i].second;
				rear++;
				q[rear] = v;
			}
		}
	}
	big = -1;
	for(i=1; i<=rear; i++){
		if(big < d[q[i]]){ big = d[q[i]]; v = q[i]; }
	}
	check[v] = true;
	d[v] = 0;
	top = 0;
	rear = 1;
	q[1] = v;
	while(true){
		top++;
		if(top > rear) break;
		for(i=0; i<edge[q[top]].size(); i++){
			nextv = edge[q[top]][i].first;
			if(!check[nextv]){
				check[nextv] = true;
				d[nextv] = d[q[top]] + edge[q[top]][i].second;
				rear++;
				q[rear] = nextv;
				path[nextv] = q[top];
			}
		}
	}
    big = -1;
    for(i=1; i<=rear; i++){
		if(big < d[q[i]]){ big = d[q[i]]; nextv = q[i]; }
    }
    tmp = big;
	r = 999999999;
	x = nextv;
	while(true){
		if(r > max(d[x],d[nextv]-d[x])){ r = max(d[x],d[nextv]-d[x]); ansv = x; }
		if(v == x) break;
		x = path[x];
	}

	/*for(i=1; i<=rear; i++) d[q[i]] = 999999999;
	d[ansv] = 0;
	top = 0; rear = 1; q[1] = ansv;
	while(true){
		top++; if(top > rear) break;
		for(i=0; i<edge[q[top]].size(); i++){
			if(d[edge[q[top]][i].first] == 999999999){
			d[edge[q[top]][i].first] = d[q[top]] + edge[q[top]][i].second;
			rear++; q[rear] = edge[q[top]][i].first; }
		}
	}
	big = -1;
	for(i=1; i<=rear; i++) if(big < d[q[i]]) big = d[q[i]];
	if(r != big) printf("%d %d\n",r,big);*/

	return r;
}

#include "dreaming.h"
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
	int i;
	int x,y,cost;
	int rear;
	//freopen("input.txt","r",stdin);

	//scanf("%d %d %d",&N,&M,&L);
	N = n; M = m; L = l;
	for(i=1; i<=N; i++) d[i] = 999999999;
	for(i=1; i<=M; i++){
		//scanf("%d %d %d",&x,&y,&cost);
		x = A[i-1]; y = B[i-1]; cost = T[i-1];
		x++; y++;
		edge[x].push_back(make_pair(y,cost));
		edge[y].push_back(make_pair(x,cost));
	}
	rear = 0;
	for(i=1; i<=N; i++){
		if(check[i]) continue;
		x = bfs(i);
		rear++;
		a[rear] = x;
		dia[rear] = tmp;
		//printf("%d\n",x);
	}
	sort(a+1,a+rear+1);
	sort(dia+1,dia+rear+1);
	if(rear == 1){
		return dia[1];
		printf("%d",dia[1]);
	}else if(rear == 2){
		return max(a[1]+a[2]+L,dia[2]);
		printf("%d",max(a[1]+a[2]+L,dia[2]));
	}else{
		return max(max(a[rear]+a[rear-1]+L,a[rear-1]+a[rear-2]+L+L),dia[rear]);
		printf("%d",max(max(a[rear]+a[rear-1]+L,a[rear-1]+a[rear-2]+L+L),dia[rear]));
	}

	return 0;
}

Compilation message (stderr)

dreaming.cpp: In function 'int bfs(int)':
dreaming.cpp:28:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<edge[q[top]].size(); i++){
            ~^~~~~~~~~~~~~~~~~~~~
dreaming.cpp:49:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<edge[q[top]].size(); i++){
            ~^~~~~~~~~~~~~~~~~~~~
dreaming.cpp:19:15: warning: variable 'ansv' set but not used [-Wunused-but-set-variable]
  int top,rear,ansv;
               ^~~~
dreaming.cpp:68:26: warning: 'nextv' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(r > max(d[x],d[nextv]-d[x])){ r = max(d[x],d[nextv]-d[x]); ansv = x; }
                   ~~~~~~~^
dreaming.cpp:41:11: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
  check[v] = true;
  ~~~~~~~~~^~~~~~

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