oj.uz

Submission #219552

# Submission time Handle Problem Language Result Execution time Memory
219552 2020-04-05T14:26:37 Z Sorting Islands (IOI08_islands) C++14
80 / 100
 566 ms 131076 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 1e6 + 7;

struct FastVector{
	long long arr[kN], sz;

	FastVector(int sz = 0){
		this->sz = sz;
	}

	void resize(int sz = 0){
		this->sz = sz;
	}

	void clear(){
		sz = 0;
	}

	void push_back(int x){
		arr[sz++] = x;
	}

	long long& operator[](int idx){
		return arr[idx];
	}

	inline int size(){
		return sz;
	}
};

vector<pair<int, int> > 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]: 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(FastVector &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]: 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]: 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;
}

FastVector path, longest_path[2];
int prohibited[2];

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;

	path.clear();
	get_path(path, back_edge.first, -1, back_edge);
	for(int i = 0; i < path.size() / 2; ++i)
		swap(path[i], path[(int)path.size() - i - 1]);

	longest_path[0].clear();
	longest_path[1].clear();
	for(int i = 0; i < 2; ++i)
		longest_path[i].resize(path.size());


	for(int i = 0; i < path.size(); ++i){
		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]: 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]: 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;

	bool to_del = false;
	int ud, tod, lend;
	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);

				to_del = true;
				ud = u;
				tod = to;
				lend = len;
			}
			continue;
		}

		build_tree(to, u, back_edges, len_back_edges);
	}

	if(to_del){
		adj[ud].erase(find(adj[ud].begin(), adj[ud].end(), pair<int, int>{tod, lend}));
		adj[tod].erase(find(adj[tod].begin(), adj[tod].end(), pair<int, int>{ud, lend}));
	}
}

vector<pair<int, int>> back_edges;
vector<int> len_back_edges;

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}); 
	}
	
	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:41:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for(auto [to, len]: adj[u]){
           ^
islands.cpp: In function 'bool get_path(FastVector&, int, int, const std::pair<int, int>&)':
islands.cpp:60:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for(auto [to, len]: adj[u]){
           ^
islands.cpp:60:19: warning: unused variable 'len' [-Wunused-variable]
  for(auto [to, len]: adj[u]){
                   ^
islands.cpp: In function 'long long int get_longest_path_length(int, int, const int*)':
islands.cpp:74:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for(auto [to, len]: adj[u]){
           ^
islands.cpp: In function 'long long int get_max_path(const std::pair<int, int>&, int)':
islands.cpp:118:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for(auto [to, len]: adj[path[i]]){
             ^
islands.cpp:131:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for(auto [to, len]: adj[path[i]]){
             ^
islands.cpp: In function 'void build_tree(int, int, std::vector<std::pair<int, int> >&, std::vector<int>&)':
islands.cpp:160: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:214: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 18 ms 23808 KB Output is correct
2 Correct 18 ms 23936 KB Output is correct
3 Correct 20 ms 23936 KB Output is correct
4 Correct 18 ms 23936 KB Output is correct
5 Correct 17 ms 23808 KB Output is correct
6 Correct 18 ms 23808 KB Output is correct
7 Correct 17 ms 23808 KB Output is correct
8 Correct 17 ms 23808 KB Output is correct
9 Correct 18 ms 23808 KB Output is correct
10 Correct 17 ms 23808 KB Output is correct
11 Correct 17 ms 23936 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23936 KB Output is correct
2 Correct 18 ms 23936 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24064 KB Output is correct
2 Correct 20 ms 24448 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25088 KB Output is correct
2 Correct 38 ms 28152 KB Output is correct
3 Correct 34 ms 25208 KB Output is correct
4 Correct 23 ms 24448 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 29560 KB Output is correct
2 Correct 60 ms 31224 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 35704 KB Output is correct
2 Correct 121 ms 44920 KB Output is correct
3 Correct 151 ms 59384 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 42872 KB Output is correct
2 Correct 243 ms 78300 KB Output is correct
3 Correct 307 ms 88696 KB Output is correct
4 Correct 345 ms 124280 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 83136 KB Output is correct
2 Runtime error 566 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 420 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -