oj.uz

답안 #468351

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
468351 2021-08-27T18:59:36 Z jazzup 꿈 (IOI13_dreaming) C++14
0 / 100
 56 ms 17592 KB 
#include "dreaming.h"
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>

using namespace std;

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

int a[100010],b[100010],c[100010];
bool shd;

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

	if(dis2[n.first]==n.second && !shd){
		double targ=n.second/2.0;
		double dd=targ;
		long long pu;
		for(long long 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);
		shd=true;
	}

	for(long long 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(long long i=0;i<n;i++){
		dis1[i]=-1;
	}

	for(long long 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(long long i=0;i<n;i++){
		if(dis1[i]==-1){
			dis1[i]=0;
			q.push(i);
			visited[i]=true;	

			long long mxd=0,nd=i;

			while(!q.empty()){
				long long cur=q.front();
				if(dis1[cur]>mxd){
					mxd=dis1[cur];
					nd=cur;
				}
				q.pop();
				for(long long 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(long long i=0;i<n;i++){
		dis1[i]=-1;
		visited[i]=false;
	}

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

		long long mxd=0,nd=i;

		while(!q.empty()){
			long long cur=q.front();
			if(dis1[cur]>mxd){
				mxd=dis1[cur];
				nd=cur;
			}
			q.pop();
			for(long long 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(long long i=0;i<n;i++){
		dis2[i]=-1;
		visited[i]=false;
	}

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

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

	long long ml=-1;

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

	long long yo=n-m;

	long long 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);
	// printf("%lld\n",yo);
    return (int)ans;
}

Compilation message

dreaming.cpp: In function 'void dfs(std::pair<long long int, long long int>)':
dreaming.cpp:27:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for(long long i=0;i<nl.size();i++){
      |                     ~^~~~~~~~~~
dreaming.cpp:38:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for(long long i=0;i<v[n.first].size();i++){
      |                    ~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:72:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(long long i=0;i<v[cur].size();i++){
      |                       ~^~~~~~~~~~~~~~
dreaming.cpp:89:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for(long long i=0;i<pa.size();i++){
      |                    ~^~~~~~~~~~
dreaming.cpp:103:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |    for(long long i=0;i<v[cur].size();i++){
      |                      ~^~~~~~~~~~~~~~
dreaming.cpp:119:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for(long long i=0;i<pb.size();i++){
      |                    ~^~~~~~~~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 17592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 17592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 8880 KB Output is correct
2 Correct 31 ms 8996 KB Output is correct
3 Correct 32 ms 8900 KB Output is correct
4 Correct 33 ms 9108 KB Output is correct
5 Correct 30 ms 8992 KB Output is correct
6 Correct 37 ms 9812 KB Output is correct
7 Correct 33 ms 9232 KB Output is correct
8 Correct 31 ms 8792 KB Output is correct
9 Correct 31 ms 8868 KB Output is correct
10 Correct 32 ms 9160 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 12 ms 8380 KB Output is correct
13 Correct 12 ms 8512 KB Output is correct
14 Correct 12 ms 8380 KB Output is correct
15 Correct 13 ms 8508 KB Output is correct
16 Correct 12 ms 8496 KB Output is correct
17 Correct 12 ms 8380 KB Output is correct
18 Correct 12 ms 8508 KB Output is correct
19 Correct 12 ms 8416 KB Output is correct
20 Incorrect 2 ms 2636 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 17592 KB Output isn't correct
2 Halted 0 ms 0 KB -