oj.uz

Submission #401413

# Submission time Handle Problem Language Result Execution time Memory
401413 2021-05-10T07:34:22 Z Jorge213 Toll (APIO13_toll) C++14
0 / 100
 1 ms 204 KB 
#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int u, v;
	long long w;
	bool operator<(const Edge &e) const {
		return w < e.w;
	}
};

struct DSU {
	vector<int> dsu;

	DSU(int n): dsu(n) {
		for (int i = 1; i < n; i++)
			dsu[i] = i;
	}

	int root(int idx) {
		while (idx != dsu[idx]) {
			dsu[idx] = dsu[dsu[idx]];
			idx = dsu[idx];
		}
		return idx;
	}

	bool join(int a, int b) {
		a = root(a);
		b = root(b);
		if (a == b)
			return false;
		dsu[b] = a;
		return true;
	}
};

struct Tree {
	vector<vector<int>> adjList;
	vector<long long> cnt;
	bool valid = true;
	DSU dsu;

	Tree(int sz, vector<long long> &a): 
		adjList(sz + 1), dsu(sz + 1), cnt(a) {};

	void addEdge(int u, int v) {
		adjList[u].emplace_back(v);
		adjList[v].emplace_back(u);
		valid = valid && dsu.join(u, v);
	}

	void dfs(int v, int p) {
		for (int u : adjList[v]) {
			if (u == p) continue;
			dfs(u, v);
			cnt[v] += cnt[u];
		}
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, m, k;
	cin >> n >> m >> k; 

	vector<Edge> edges, nedges;
	vector<long long> a(n + 1);

	int ai, bi;
	long long ci;
	for (int i = 0; i < m; i++) {
		cin >> ai >> bi >> ci;
		edges.push_back({ai, bi, ci});
	}

	sort(edges.begin(), edges.end());

	int xi, yi;
	for (int i = 0; i < k; i++) {
		cin >> xi >> yi;
		nedges.push_back({xi, yi, 0});
	}

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	DSU dsu(n + 1), ndsu(n + 1);

	for (auto [u, v, w] : nedges) {
		ndsu.join(u, v);
	}

	for (auto [u, v, w] : edges) {
		u = dsu.root(u), v = dsu.root(v);
		if (ndsu.root(u) != ndsu.root(v)) 
			dsu.join(u, v);
	}

	int sz = 0;
	vector<int> comp(n + 1, 0);
	vector<long long> p = {0};

	for (int i = 1; i <= n; i++) {
		int v = dsu.root(i);
		if (!comp[v]) {
			comp[v] = ++sz;
			p.push_back(0);
		}
		comp[i] = comp[v];
		p[comp[i]] += a[i];
	}


	vector<long long> mnw = {0};
	for (auto [u, v, w] : edges) {
		u = comp[u], v = comp[v];
		if (u != v)
			mnw.push_back(w);
	}

	for (auto &[u, v, w] : nedges) {
		u = comp[u], v = comp[v];
	}

	long long ans = 0;
	for (int bm = 1; bm < (1 << k); bm++) {
		if (__builtin_popcount(bm) < sz - 1) 
			continue;

		Tree g(sz, p);
		for (int i = 0; i < k; i++) {
			if (!(bm & (1 << i))) continue;
			g.addEdge(nedges[i].u, nedges[i].v);
		}

		if (!g.valid)
			continue;

		g.dfs(1, -1);
		sort(g.cnt.begin(), g.cnt.end());

		long long can = 0;
		for (int i = 1; i < sz; i++) {
			can += mnw[i] * g.cnt[i];
		}

		ans = max(ans, can);
	}

	cout << ans << '\n';

	return 0;
}

Compilation message

toll.cpp: In constructor 'Tree::Tree(int, std::vector<long long int>&)':
toll.cpp:42:6: warning: 'Tree::dsu' will be initialized after [-Wreorder]
   42 |  DSU dsu;
      |      ^~~
toll.cpp:40:20: warning:   'std::vector<long long int> Tree::cnt' [-Wreorder]
   40 |  vector<long long> cnt;
      |                    ^~~
toll.cpp:44:2: warning:   when initialized here [-Wreorder]
   44 |  Tree(int sz, vector<long long> &a):
      |  ^~~~
toll.cpp: In function 'int main()':
toll.cpp:93:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |  for (auto [u, v, w] : nedges) {
      |            ^
toll.cpp:97:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |  for (auto [u, v, w] : edges) {
      |            ^
toll.cpp:119:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |  for (auto [u, v, w] : edges) {
      |            ^
toll.cpp:125:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |  for (auto &[u, v, w] : nedges) {
      |             ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -