oj.uz

Submission #403602

# Submission time Handle Problem Language Result Execution time Memory
403602 2021-05-13T10:00:11 Z mshandilya Dreaming (IOI13_dreaming) C++14
32 / 100
 112 ms 25496 KB 
#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.resize(N);
	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());
	for(int i = trees.size()-1; i>0; i--) {
		max_length_path = max(max_length_path, trees[i-1]+trees[i]+L);
		trees[i-1] = max(trees[i], L+trees[i-1]);
	}
    return max_length_path;
}

Compilation message

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 25496 KB Output is correct
2 Correct 112 ms 25040 KB Output is correct
3 Correct 64 ms 18664 KB Output is correct
4 Correct 11 ms 3916 KB Output is correct
5 Correct 9 ms 2764 KB Output is correct
6 Correct 25 ms 5824 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 63 ms 11072 KB Output is correct
9 Correct 64 ms 15192 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 101 ms 19292 KB Output is correct
12 Correct 111 ms 22136 KB Output is correct
13 Correct 1 ms 460 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 25496 KB Output is correct
2 Correct 112 ms 25040 KB Output is correct
3 Correct 64 ms 18664 KB Output is correct
4 Correct 11 ms 3916 KB Output is correct
5 Correct 9 ms 2764 KB Output is correct
6 Correct 25 ms 5824 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 63 ms 11072 KB Output is correct
9 Correct 64 ms 15192 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 101 ms 19292 KB Output is correct
12 Correct 111 ms 22136 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Incorrect 1 ms 204 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 14364 KB Output is correct
2 Correct 47 ms 14328 KB Output is correct
3 Correct 52 ms 14244 KB Output is correct
4 Correct 45 ms 14272 KB Output is correct
5 Correct 43 ms 14272 KB Output is correct
6 Correct 48 ms 15336 KB Output is correct
7 Correct 49 ms 14908 KB Output is correct
8 Correct 47 ms 14024 KB Output is correct
9 Correct 43 ms 13900 KB Output is correct
10 Correct 49 ms 14788 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 10 ms 8428 KB Output is correct
13 Correct 11 ms 8400 KB Output is correct
14 Correct 9 ms 8392 KB Output is correct
15 Correct 10 ms 8368 KB Output is correct
16 Correct 9 ms 8392 KB Output is correct
17 Correct 12 ms 8392 KB Output is correct
18 Correct 10 ms 8520 KB Output is correct
19 Correct 10 ms 8392 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 10 ms 8356 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 25496 KB Output is correct
2 Correct 112 ms 25040 KB Output is correct
3 Correct 64 ms 18664 KB Output is correct
4 Correct 11 ms 3916 KB Output is correct
5 Correct 9 ms 2764 KB Output is correct
6 Correct 25 ms 5824 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 63 ms 11072 KB Output is correct
9 Correct 64 ms 15192 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 101 ms 19292 KB Output is correct
12 Correct 111 ms 22136 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Incorrect 1 ms 204 KB Output isn't correct
15 Halted 0 ms 0 KB -