Submission #167476

#	Time	Username	Problem	Language	Result	Execution time	Memory
167476		nikatamliani	Dreaming (IOI13_dreaming)	C++14	100 / 100	177 ms	17436 KiB

dreaming

# include "dreaming.h"
# include <bits/stdc++.h>
using namespace std; 
const int N = 2e5 + 10;
int fix[N], ans = 0;
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){
			dist[edges[x][i].first] = dist[x] + edges[x][i].second;
			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, 0), dist_b(N, 0), 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();
			dist_a[i] = 0;  
			dfs(i, -1, 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();
			dist_a[a] = 0;
			dfs(a, -1, 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]; 
			}
			ans = max(ans, dist_a[b]);  
			pts.clear();
			dist_b[b] = 0;
			dfs(b, -1, dist_b);
			int res = 1e9 * 2;
			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();
		}
	}
 	sort(cen.rbegin(), cen.rend());
    int res = ans;
    if(cen.size() >= 2) res = max(res, cen[0] + cen[1] + L);
    if(cen.size() >= 3) res = max(res, cen[1] + cen[2] + 2 * L); 
    return res;
}

Compilation message (stderr)

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:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < pts.size(); i ++){
                   ~~^~~~~~~~~~~~
dreaming.cpp:37:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < pts.size(); i ++){
                   ~~^~~~~~~~~~~~
dreaming.cpp:45:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < pts.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