oj.uz

Submission #219577

# Submission time Handle Problem Language Result Execution time Memory
219577 2020-04-05T15:50:25 Z Sorting Islands (IOI08_islands) C++14
0 / 100
 2000 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], 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}); 
	}
	
	for(int i = 1; i <= n; ++i)
		if(!vis[i])
			build_tree(i, -1, back_edges, len_back_edges);

	while(true);

	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:210: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 2084 ms 47360 KB Time limit exceeded
2 Execution timed out 2091 ms 47352 KB Time limit exceeded
3 Execution timed out 2080 ms 47360 KB Time limit exceeded
4 Execution timed out 2095 ms 47352 KB Time limit exceeded
5 Execution timed out 2093 ms 47360 KB Time limit exceeded
6 Execution timed out 2095 ms 47360 KB Time limit exceeded
7 Execution timed out 2096 ms 47360 KB Time limit exceeded
8 Execution timed out 2098 ms 47360 KB Time limit exceeded
9 Execution timed out 2094 ms 47360 KB Time limit exceeded
10 Execution timed out 2090 ms 47360 KB Time limit exceeded
11 Execution timed out 2097 ms 47360 KB Time limit exceeded

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2092 ms 47488 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 2089 ms 47480 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 2097 ms 48888 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 2090 ms 54136 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 2082 ms 67448 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 2078 ms 80376 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 2091 ms 131072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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