oj.uz

Submission #219570

# Submission time Handle Problem Language Result Execution time Memory
219570 2020-04-05T15:35:00 Z Sorting Islands (IOI08_islands) C++14
70 / 100
 547 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);

	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:208: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 41 ms 47268 KB Output is correct
2 Correct 33 ms 47352 KB Output is correct
3 Correct 32 ms 47352 KB Output is correct
4 Correct 32 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 33 ms 47352 KB Output is correct
8 Correct 35 ms 47488 KB Output is correct
9 Correct 33 ms 47360 KB Output is correct
10 Correct 32 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 32 ms 47488 KB Output is correct
2 Correct 33 ms 47488 KB Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 49016 KB Output is correct
2 Correct 60 ms 52600 KB Output is correct
3 Correct 46 ms 49272 KB Output is correct
4 Correct 40 ms 48384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 54648 KB Output is correct
2 Correct 90 ms 58616 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 66808 KB Output is correct
2 Correct 167 ms 74360 KB Output is correct
3 Correct 191 ms 88440 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 80376 KB Output is correct
2 Correct 310 ms 119416 KB Output is correct
3 Correct 384 ms 123512 KB Output is correct
4 Runtime error 328 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 423 ms 131072 KB Output is correct
2 Runtime error 547 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 431 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -