oj.uz

Submission #219540

# Submission time Handle Problem Language Result Execution time Memory
219540 2020-04-05T13:51:29 Z Sorting Islands (IOI08_islands) C++14
70 / 100
 573 ms 131076 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 1e6 + 7;

vector<pair<int, int> > adj[kN], new_adj[kN];	
bool vis[kN];
int depth[kN];

pair<long long, long long> get_diameter_length(int u, int par){
	pair<long long, long long> ans{0, 0};
	for(auto [to, len]: new_adj[u]){
		if(to == par)
			continue;

		auto d = get_diameter_length(to, u);
		ans.first = max(ans.first, d.first);
		ans.first = max(ans.first, d.second + len + ans.second);
		ans.second = max(ans.second, d.second + len);
	}

	return ans;
}

bool get_path(vector<int> &path, int u, int par, const pair<int, int> &back_edge){
	if(u == back_edge.second){
		path.push_back(u);
		return true;
	}

	for(auto [to, len]: new_adj[u]){
		if(to == par )
			continue;

		if(get_path(path, to, u, back_edge)){
			path.push_back(u);
			return true;
		}
	}
	return false;
}

long long get_longest_path_length(int u, int par, const int prohibited[]){
	long long ans = 0;
	for(auto [to, len]: new_adj[u]){
		if(to == par || to == prohibited[0] || to == prohibited[1])
			continue;

		ans = max(ans, get_longest_path_length(to, u, prohibited) + len);
	}
	return ans;
}

long long get_max_path(const pair<int, int> &back_edge, const int len_back_edge){
	long long ans = get_diameter_length(back_edge.first, -1).first;

	vector<int> path;
	get_path(path, back_edge.first, -1, back_edge);
	reverse(path.begin(), path.end());

	vector<long long> longest_path[2];
	for(int i = 0; i < 2; ++i)
		longest_path[i].resize(path.size());

	for(int i = 0; i < path.size(); ++i){
		int prohibited[2];

		if(i == 0)
			prohibited[0] = -1;
		else
			prohibited[0] = path[i - 1];

		if(i == path.size() - 1)
			prohibited[1] = -1;
		else
			prohibited[1] = path[i + 1]; 

		longest_path[0][i] = longest_path[1][i] = get_longest_path_length(path[i], -1, prohibited);
	}

	long long curr_len = 0;
	for(int i = 0; i < path.size(); ++i){
		longest_path[0][i] += curr_len;
		if(i != (int)path.size() - 1){
			for(auto [to, len]: new_adj[path[i]]){
				if(to == path[i + 1]){
					curr_len += len;
					break;
				}
			}
		}
	}

	curr_len = 0;
	for(int i = (int)path.size() - 1; i >= 0; --i){
		longest_path[1][i] += curr_len;
		if(i != 0){
			for(auto [to, len]: new_adj[path[i]]){
				if(to == path[i - 1]){
					curr_len += len;
					break;
				}
			}
		}
	}

	for(int i = 1; i < path.size(); ++i)
		longest_path[0][i] = max(longest_path[0][i - 1], longest_path[0][i]);
	for(int i = (int)path.size() - 2; i >= 0; --i)
		longest_path[1][i] = max(longest_path[1][i + 1], longest_path[1][i]);

	for(int i = 0; i < (int)path.size() - 1; ++i)
		ans = max(ans, longest_path[0][i] + longest_path[1][i + 1] + len_back_edge);

	return ans;	
}

void build_tree(int u, int par, vector<pair<int, int>> &back_edges, vector<int> &len_back_edges){
	vis[u] = true;
	if(par == -1)
		depth[u] = 0;
	else
		depth[u] = depth[par] + 1;

	for(auto [to, len]: adj[u]){
		if(to == par)
			continue;
		if(vis[to]){
			if(depth[to] > depth[u]){
				back_edges.push_back({to, u});
				len_back_edges.push_back(len);
			}
			continue;
		}

		build_tree(to, u, back_edges, len_back_edges);
		new_adj[u].push_back({to, len});
		new_adj[to].push_back({u, len});
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;

	for(int u = 1; u <= n; ++u){
		int v, len;
		cin >> v >> len;

		adj[u].push_back({v, len});
		adj[v].push_back({u, len}); 
	}

	vector<pair<int, int>> back_edges;
	vector<int> len_back_edges;
	for(int i = 1; i <= n; ++i)
		if(!vis[i])
			build_tree(i, -1, back_edges, len_back_edges);

	for(int i = 1; i <= n; ++i)
		vis[i] = false;

	long long ans = 0;
	for(int i = 0; i < back_edges.size(); ++i)
		ans += get_max_path(back_edges[i], len_back_edges[i]);

	cout << ans << "\n";
}

Compilation message

islands.cpp: In function 'std::pair<long long int, long long int> get_diameter_length(int, int)':
islands.cpp:13:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for(auto [to, len]: new_adj[u]){
           ^
islands.cpp: In function 'bool get_path(std::vector<int>&, int, int, const std::pair<int, int>&)':
islands.cpp:32:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for(auto [to, len]: new_adj[u]){
           ^
islands.cpp:32:19: warning: unused variable 'len' [-Wunused-variable]
  for(auto [to, len]: new_adj[u]){
                   ^
islands.cpp: In function 'long long int get_longest_path_length(int, int, const int*)':
islands.cpp:46:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for(auto [to, len]: new_adj[u]){
           ^
islands.cpp: In function 'long long int get_max_path(const std::pair<int, int>&, int)':
islands.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < path.size(); ++i){
                 ~~^~~~~~~~~~~~~
islands.cpp:74:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i == path.size() - 1)
      ~~^~~~~~~~~~~~~~~~~~
islands.cpp:83:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < path.size(); ++i){
                 ~~^~~~~~~~~~~~~
islands.cpp:86:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for(auto [to, len]: new_adj[path[i]]){
             ^
islands.cpp:99:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for(auto [to, len]: new_adj[path[i]]){
             ^
islands.cpp:108:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < path.size(); ++i)
                 ~~^~~~~~~~~~~~~
islands.cpp: In function 'void build_tree(int, int, std::vector<std::pair<int, int> >&, std::vector<int>&)':
islands.cpp:126:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for(auto [to, len]: adj[u]){
           ^
islands.cpp: In function 'int main()':
islands.cpp:168:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < back_edges.size(); ++i)
                 ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47352 KB Output is correct
2 Correct 32 ms 47360 KB Output is correct
3 Correct 33 ms 47360 KB Output is correct
4 Correct 33 ms 47360 KB Output is correct
5 Correct 33 ms 47360 KB Output is correct
6 Correct 32 ms 47360 KB Output is correct
7 Correct 32 ms 47360 KB Output is correct
8 Correct 33 ms 47424 KB Output is correct
9 Correct 33 ms 47360 KB Output is correct
10 Correct 34 ms 47360 KB Output is correct
11 Correct 32 ms 47360 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47480 KB Output is correct
2 Correct 34 ms 47488 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47488 KB Output is correct
2 Correct 35 ms 48000 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 48936 KB Output is correct
2 Correct 59 ms 52560 KB Output is correct
3 Correct 47 ms 49272 KB Output is correct
4 Correct 40 ms 48248 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 54908 KB Output is correct
2 Correct 84 ms 58692 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 68216 KB Output is correct
2 Correct 165 ms 75668 KB Output is correct
3 Correct 194 ms 90484 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 85240 KB Output is correct
2 Correct 322 ms 123888 KB Output is correct
3 Correct 370 ms 128364 KB Output is correct
4 Runtime error 339 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 131072 KB Output is correct
2 Runtime error 573 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 409 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -