Submission #406705

#	Time	Username	Problem	Language	Result	Execution time	Memory
406705		mshandilya	Dreaming (IOI13_dreaming)	C++14	32 / 100	131 ms	25536 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

std::vector<std::list<pair<int, int>>> adj_list;
int max_length_path = 0;

void dfs(int root, std::vector<int>& parent, std::vector<std::vector<int>>& pre_long, std::vector<std::vector<int>>& post_long) {
	int child = 0;
	for(auto& i : adj_list[root])
		if(i.first!=parent[root]) {
			parent[i.first] = root;
			dfs(i.first, parent, pre_long, post_long);
			if(child>0)
				pre_long[root][child] = max(pre_long[root][child-1], i.second + (adj_list[i.first].size()>1?pre_long[i.first][0]:0));
			else
				pre_long[root][child] = i.second + (adj_list[i.first].size()>1?pre_long[i.first][0]:0);
			post_long[root][child] = i.second + (adj_list[i.first].size()>1?pre_long[i.first][0]:0);
			child++;
		}
	return;
}

int findLongestDistances(int root, std::vector<int>& parent, std::vector<std::vector<int>>& pre_long, std::vector<std::vector<int>>& post_long) {
	int child = 0;
	for(int i = post_long[root].size()-2; i>=0; i--)
	    post_long[root][i] = max(post_long[root][i], post_long[root][i+1]);
	int min_dist = (adj_list[root].size()>0)?post_long[root][0]:0;
	max_length_path = max(max_length_path, min_dist);  
	for(auto& i : adj_list[root])
		if(i.first!=parent[root]) {
			post_long[i.first][adj_list[i.first].size()-1] =  max(child>0?pre_long[root][child-1]:0, child<(adj_list[root].size()-1)?post_long[root][child+1]:0) + i.second;
			if(adj_list[i.first].size()>1)
			    pre_long[i.first][adj_list[i.first].size()-1] = max(pre_long[i.first][adj_list[i.first].size()-2], post_long[i.first][adj_list[i.first].size()-1]);
			else
			    pre_long[i.first][adj_list[i.first].size()-1] = post_long[i.first][adj_list[i.first].size()-1];
			min_dist = min(min_dist, findLongestDistances(i.first, parent, pre_long, post_long));
			child++;
		}
	return min_dist;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	adj_list.assign(N, std::list<pair<int, int>> ());
	max_length_path = 0;
	std::vector<std::vector<int>> pre_long(N, std::vector<int> ()), post_long(N, std::vector<int> ());
	std::vector<int> parent(N, -1), trees;
	for(int i = 0; i<M; i++) {
		adj_list[A[i]].push_back({B[i], T[i]});
		adj_list[B[i]].push_back({A[i], T[i]});
	}
	for(int i = 0; i<N; i++) {
		pre_long[i].resize(adj_list[i].size());
		post_long[i].resize(adj_list[i].size());
	}
	for(int i = 0; i<N; i++) {
		if(parent[i]==-1) {
			dfs(i, parent, pre_long, post_long);
			int dist = findLongestDistances(i, parent, pre_long, post_long);
			trees.push_back(dist);
		}
	}
	sort(trees.begin(), trees.end());
	int i = trees.size()-1;
	if(trees.size()>1) {
		max_length_path = max(max_length_path, trees[i-1]+trees[i]+L);
		if(trees.size()>2)
			max_length_path = max(max_length_path, trees[i-1]+trees[i-2]+2*L);
	}
    return max_length_path;
}

Compilation message (stderr)

dreaming.cpp: In function 'int findLongestDistances(int, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)':
dreaming.cpp:33:98: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::list<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    post_long[i.first][adj_list[i.first].size()-1] =  max(child>0?pre_long[root][child-1]:0, child<(adj_list[root].size()-1)?post_long[root][child+1]:0) + i.second;
      |                                                                                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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