제출 #468326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
468326		jazzup	Dreaming (IOI13_dreaming)	C++14	32 / 100	74 ms	16280 KiB

dreaming

#include "dreaming.h"
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>

using namespace std;

int dis1[100010],dis2[100010];
bool visited[100010];
vector<pair<int,int> > v[100010],pb;
vector<int> pa,nl,len;
queue<int> q;

void dfs(pair<int,int> n){
	visited[n.first]=true;
	nl.push_back(n.first);

	if(dis2[n.first]==n.second){
		double targ=n.second/2.0;
		double dd=targ;
		int pu;
		for(int i=0;i<nl.size();i++){
			double diff=abs((double)dis2[nl[i]]-targ);
			if(diff<=dd){
				dd=diff;
				pu=max(dis2[nl[i]],n.second-dis2[nl[i]]);
			}
		}
		len.push_back(pu);
	}

	for(int i=0;i<v[n.first].size();i++){
		if(!visited[v[n.first][i].first]){
			dis2[v[n.first][i].first]=dis2[n.first]+v[n.first][i].second;
			dfs(make_pair(v[n.first][i].first,n.second));
		}
	}
	nl.pop_back();
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]){
	for(int i=0;i<n;i++){
		dis1[i]=-1;
	}

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

	for(int i=0;i<n;i++){
		if(dis1[i]==-1){
			dis1[i]=0;
			q.push(i);
			visited[i]=true;	

			int mxd=0,nd=i;

			while(!q.empty()){
				int cur=q.front();
				if(dis1[cur]>mxd){
					mxd=dis1[cur];
					nd=cur;
				}
				q.pop();
				for(int i=0;i<v[cur].size();i++){
					if(!visited[v[cur][i].first]){
						q.push(v[cur][i].first);
						dis1[v[cur][i].first]=dis1[cur]+v[cur][i].second;
						visited[v[cur][i].first]=true;
					}
				}
			}
			pa.push_back(nd);
		}
	}

	for(int i=0;i<n;i++){
		dis1[i]=-1;
		visited[i]=false;
	}

	for(int i=0;i<pa.size();i++){
		dis1[pa[i]]=0;
		q.push(pa[i]);
		visited[pa[i]]=true;	

		int mxd=0,nd=i;

		while(!q.empty()){
			int cur=q.front();
			if(dis1[cur]>mxd){
				mxd=dis1[cur];
				nd=cur;
			}
			q.pop();
			for(int i=0;i<v[cur].size();i++){
				if(!visited[v[cur][i].first]){
					q.push(v[cur][i].first);
					dis1[v[cur][i].first]=dis1[cur]+v[cur][i].second;
					visited[v[cur][i].first]=true;
				}
			}
		}
		pb.push_back(make_pair(nd,mxd));
	}

	for(int i=0;i<n;i++){
		dis2[i]=-1;
		visited[i]=false;
	}

	for(int i=0;i<pb.size();i++){
		dis2[pb[i].first]=0;
		dfs(pb[i]);
	}

	sort(len.begin(),len.end());

	int ml=-1;

	for(int i=0;i<n;i++){
		if(dis2[i]>ml){
			ml=dis2[i];
		}
	}

	int yo=len.size();

	int ans=-1;

	if(yo>=3){
		ans=max(len[yo-1]+len[yo-2]+l,len[yo-3]+len[yo-2]+2*l);
	}

	else if(yo==2){
		ans=len[yo-1]+len[yo-2]+l;
	}

	ans=max(ans,ml);

    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

dreaming.cpp: In function 'void dfs(std::pair<int, int>)':
dreaming.cpp:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int i=0;i<nl.size();i++){
      |               ~^~~~~~~~~~
dreaming.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=0;i<v[n.first].size();i++){
      |              ~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:68: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]
   68 |     for(int i=0;i<v[cur].size();i++){
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp:85:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for(int i=0;i<pa.size();i++){
      |              ~^~~~~~~~~~
dreaming.cpp:99:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |    for(int i=0;i<v[cur].size();i++){
      |                ~^~~~~~~~~~~~~~
dreaming.cpp:115:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for(int i=0;i<pb.size();i++){
      |              ~^~~~~~~~~~

• 서브태스크 1: 14 / 14
• 서브태스크 2: 0 / 10
• 서브태스크 3: 0 / 23
• 서브태스크 4: 18 / 18
• 서브태스크 5: 0 / 12
• 서브태스크 6: 0 / 23