Submission #219552

#	Time	Username	Problem	Language	Result	Execution time	Memory
219552		Sorting	Islands (IOI08_islands)	C++14	80 / 100	566 ms	131076 KiB

islands

#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 (stderr)

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 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10