oj.uz

Submission #219727

# Submission time Handle Problem Language Result Execution time Memory
219727 2020-04-06T06:44:36 Z Sorting Islands (IOI08_islands) C++14
0 / 100
 2000 ms 101972 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], 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(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]: 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;
}

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]: 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});
	}
}

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}); 
	}

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

	

	int memory = sizeof(adj) + sizeof(new_adj) + sizeof(back_edges) + sizeof(len_back_edges) + sizeof(path) + sizeof(longest_path);
	memory += sizeof(vis) + sizeof(depth);
	memory /= 1024;
	memory /= 1024;
	memory /= 8;

	while(memory >= 50);

	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]: new_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]: new_adj[u]){
           ^
islands.cpp:60: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:74: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:117:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for(auto [to, len]: new_adj[path[i]]){
             ^
islands.cpp:130:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for(auto [to, len]: new_adj[path[i]]){
             ^
islands.cpp: In function 'void build_tree(int, int, std::vector<std::pair<int, int> >&, std::vector<int>&)':
islands.cpp:157: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:212:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < back_edges.size(); ++i)
                 ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 47360 KB Time limit exceeded
2 Execution timed out 2088 ms 47360 KB Time limit exceeded
3 Execution timed out 2087 ms 47360 KB Time limit exceeded
4 Execution timed out 2087 ms 47360 KB Time limit exceeded
5 Execution timed out 2090 ms 47360 KB Time limit exceeded
6 Execution timed out 2091 ms 47360 KB Time limit exceeded
7 Execution timed out 2088 ms 47360 KB Time limit exceeded
8 Execution timed out 2085 ms 47360 KB Time limit exceeded
9 Execution timed out 2088 ms 47360 KB Time limit exceeded
10 Execution timed out 2093 ms 47360 KB Time limit exceeded
11 Execution timed out 2088 ms 47352 KB Time limit exceeded

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2097 ms 47360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2092 ms 47352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2091 ms 48128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2092 ms 49912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2091 ms 57112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2088 ms 66940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2088 ms 101972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2084 ms 94072 KB Time limit exceeded
2 Halted 0 ms 0 KB -