oj.uz

Submission #1046334

# Submission time Handle Problem Language Result Execution time Memory
1046334 2024-08-06T13:04:45 Z xnqs Cheap flights (LMIO18_pigus_skrydziai) C++17
0 / 100
 139 ms 78340 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <tuple>
#include <numeric>

class DSU {
private:
	std::vector<int> t;
	std::vector<int> sz;
public:
	DSU(int n) {
		t.assign(n,0); std::iota(t.begin(),t.end(),0);
		sz.assign(n,1);
	}

	int Find(int k) {
		if (t[k]!=k) return t[k] = Find(t[k]);
		return k;
	}

	int Unite(int a, int b) {
		int ra = Find(a);
		int rb = Find(b);

		if (ra==rb) {
			return 0;
		}

		if (sz[ra]<sz[rb]) {
			std::swap(ra,rb);
		}

		sz[ra] += sz[rb];
		t[rb] = ra;
		return 1;
	}
};

int gs, edg;
std::vector<std::vector<std::pair<int,int>>> adj_list;
std::vector<std::vector<std::pair<int,int>>> mst_adj_list;
std::vector<std::tuple<int,int,int>> edges;
std::vector<bool> edge_in_mst;
int depth[500005];
int up[19][500005];
int64_t dist[500005];

int64_t stars() {
	int64_t ans = 0;
	for (int i = 1; i <= gs; i++) {
		int64_t cand = 0;
		for (const auto& [j, w] : adj_list[i]) {
			cand += w;
		}
		ans = std::max(ans,cand);
	}
	return ans;
}

void dfs1(int k, int p) {
	depth[k] = depth[p]+1;
	up[0][k] = p;

	for (const auto& [i, w] : mst_adj_list[k]) {
		if (i!=p) {
			dist[i] = dist[k]+w;
			dfs1(i,k);
		}
	}
}

void preprocess_binary_lifting() {
	for (int l = 1; l < 19; l++) {
		for (int i = 1; i <= gs; i++) {
			up[l][i] = up[l-1][up[l-1][i]];
		}
	}
}

int kth_ancestor(int node, int k) {
	while (k) {
		int lvl = 31-__builtin_clz(k);
		node = up[lvl][node];
		k ^= (1<<lvl);
	}
	return node;
}

int get_lca(int a, int b) {
	if (depth[a]>depth[b]) {
		std::swap(a,b);
	}

	b = kth_ancestor(b,depth[b]-depth[a]);
	for (int lvl = 18; a != b;) {
		while (lvl-1>=0&&up[lvl][a]==up[lvl][b]) {
			--lvl;
		}
		a = up[lvl][a];
		b = up[lvl][b];
	}

	return a;
}

int get_dist(int a, int b) {
	return depth[a] + depth[b] - 2*depth[get_lca(a,b)];
}

int64_t get_dist_w(int a, int b) {
	return dist[a] + dist[b] - 2*dist[get_lca(a,b)];
}

int64_t triangles() {
	std::sort(edges.begin(),edges.end(),[](const std::tuple<int,int,int>& a, const std::tuple<int,int,int>& b) {
		return std::get<2>(a) > std::get<2>(b);
	});

	DSU dsu(gs+1);
	int64_t mst_cost = 0;
	for (int i = 0; i < edg; i++) {
		const auto& [a, b, c] = edges[i];
		int ra = dsu.Find(a);
		int rb = dsu.Find(b);
		if (ra!=rb) {
			edge_in_mst[i] = 1;
			mst_adj_list[a].emplace_back(b,c);
			mst_adj_list[b].emplace_back(a,c);
			dsu.Unite(ra,rb);
			mst_cost += c;
		}
	}

	dfs1(1,0);
	preprocess_binary_lifting();

	int64_t ans = 0;
	for (int i = 0; i < edg; i++) {
		if (edge_in_mst[i]) {
			continue;
		}

		const auto& [a, b, c] = edges[i];
		if (get_dist(a,b)==2) {
			ans = std::max(ans, get_dist_w(a,b)+c);
		}
	}

	return ans;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
 
	std::cin >> gs >> edg;
	adj_list.resize(gs+1);
	mst_adj_list.resize(gs+1);
	edge_in_mst.assign(edg,0);

	for (int i = 0, a, b, c; i < edg; i++) {
		std::cin >> a >> b >> c;
		adj_list[a].emplace_back(b,c);
		adj_list[b].emplace_back(a,c);
		edges.emplace_back(a,b,c);
	}

	// try all star graphs
	int64_t ans = stars();
 
	// try all "triangle" cycles
	ans = std::max(ans, triangles());
 
	std::cout << ans << "\n";
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 37208 KB Output is correct
2 Correct 3 ms 37352 KB Output is correct
3 Correct 3 ms 37212 KB Output is correct
4 Correct 3 ms 37400 KB Output is correct
5 Correct 3 ms 37396 KB Output is correct
6 Correct 7 ms 38040 KB Output is correct
7 Correct 3 ms 37212 KB Output is correct
8 Correct 3 ms 37368 KB Output is correct
9 Correct 3 ms 37212 KB Output is correct
10 Correct 3 ms 37408 KB Output is correct
11 Incorrect 4 ms 37212 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 37208 KB Output is correct
2 Correct 3 ms 37352 KB Output is correct
3 Correct 3 ms 37212 KB Output is correct
4 Correct 3 ms 37400 KB Output is correct
5 Correct 3 ms 37396 KB Output is correct
6 Correct 7 ms 38040 KB Output is correct
7 Correct 3 ms 37212 KB Output is correct
8 Correct 3 ms 37368 KB Output is correct
9 Correct 3 ms 37212 KB Output is correct
10 Correct 3 ms 37408 KB Output is correct
11 Incorrect 4 ms 37212 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 76324 KB Output is correct
2 Correct 139 ms 78340 KB Output is correct
3 Incorrect 39 ms 50692 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 76324 KB Output is correct
2 Correct 139 ms 78340 KB Output is correct
3 Incorrect 39 ms 50692 KB Output isn't correct
4 Halted 0 ms 0 KB -