oj.uz

답안 #167462

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167462 2019-12-08T15:46:51 Z nikatamliani 꿈 (IOI13_dreaming) C++14
0 / 100
 70 ms 14204 KB 
# include "dreaming.h"
# include <bits/stdc++.h>
using namespace std; 
const int N = 2e5 + 10;
int fix[N];
vector < int > pts;
vector < pair < int , int > > edges[N];
void dfs(int x, int p, vector < int > &dist){
	fix[x] = 1;
	pts.push_back(x);
	for(int i = 0; i < edges[x].size(); i ++){
		if(edges[x][i].first != p){
			dfs(edges[x][i].first, x, dist);
		}
	}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
	vector < int > dist_a(N), dist_b(N), cen;
	for(int i = 0; i < M; i ++){
		edges[A[i]].push_back(make_pair(B[i], T[i]));
		edges[B[i]].push_back(make_pair(A[i], T[i]));
	}
	for(int i = 0; i < N; i ++){
		if(fix[i] != 1){
			pts.clear();
			dfs(i, 0, dist_a);
			int a = pts[0];
			for(int i = 0; i < pts.size(); i ++){
				if(dist_a[pts[i]] < dist_a[a]) a = pts[i];
			}
			pts.clear();
			dfs(a, 0, dist_a);
			int b = pts[0];
			for(int i = 0; i < pts.size(); i ++){
				if(dist_a[pts[i]] < dist_a[b]) b = pts[i]; 
			}
			if(M == N - 1) return dist_a[b];
			pts.clear();
			dfs(b, 0, dist_b);
			int res = 1e9;
			for(int i = 0; i < pts.size(); i ++){
				res = min(res, max(dist_a[pts[i]], dist_b[pts[i]]));
			}
			cen.push_back(res);
			pts.clear();
		}
	}
	if(cen.size() == 1) return cen.back();
	else{
        sort(cen.rbegin(), cen.rend());
        int res = 0;
        if(cen.size() >= 2) res = cen[0] + cen[1] + L;
        if(cen.size() >= 3) res = max(res, cen[1] + cen[2] + 2 * L); 
        return res;
	}
}

Compilation message

dreaming.cpp: In function 'void dfs(int, int, std::vector<int>&)':
dreaming.cpp:11:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < edges[x].size(); i ++){
                 ~~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:28:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < pts.size(); i ++){
                   ~~^~~~~~~~~~~~
dreaming.cpp:34:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < pts.size(); i ++){
                   ~~^~~~~~~~~~~~
dreaming.cpp:41:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < pts.size(); i ++){
                   ~~^~~~~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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