oj.uz

답안 #401823

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401823 2021-05-10T21:22:31 Z Jorge213 통행료 (APIO13_toll) C++17
100 / 100
 1724 ms 11940 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 1e5 + 10;
const int K = 25;
int a[N], comp[N];
long long p[K];

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

struct DSU {
	int dsu[N];

	void clear(int n) {
		for (int i = 0; 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) {
		if (root(a) == root(b))
			return false;
		dsu[root(a)] = root(b);
		return true;
	}
};

struct Tree {
	vector<pii> adjList[K];
	int we[K], d[K], par[K];
	long long cnt[N];

	void clear(int n) {
		for (int i = 1; i <= n; i++) {
			adjList[i].clear();
			cnt[i] = p[i];
		}
	}

	void addEdge(int u, int v, int w) {
		adjList[u].push_back({v, w});
		adjList[v].push_back({u, w});
	}

	void dfs(int v, int p) {
		par[v] = p;
		d[v] = d[p] + 1;
		for (auto [u, w] : adjList[v]) {
			if (u == p) continue;
			dfs(u, v);
			we[u] = w;
			cnt[v] += cnt[u];
		}
	}
};

DSU dsu, ndsu;
Tree g;

int main() {
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);

	vector<Edge> edges, nedges;

	int ai, bi, ci;
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &ai, &bi, &ci);
		edges.push_back({ai, bi, ci});
	}

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

	int xi, yi;
	for (int i = 0; i < k; i++) {
		scanf("%d %d", &xi, &yi);
		nedges.push_back({xi, yi, 0});
	}

	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
	}

	int edgs = 0;

	dsu.clear(n);
	ndsu.clear(n);
	for (auto [u, v, w] : nedges) {
		if (ndsu.join(u, v))
			edgs++;
	}
	for (auto [u, v, w] : edges) {
		if (ndsu.join(u, v)) {
			dsu.join(u, v);
			edgs++;
			if (edgs == n - 1) break;
		}
	}

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

	for (int i = 1; i <= n; i++) {
		p[comp[i]] += (long long) a[i];
	}

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

	dsu.clear(sz);
	vector<Edge> mn;
	edgs = 0;

	for (auto [u, v, w] : edges) {
		if (dsu.join(comp[u], comp[v])) {
			mn.push_back({comp[u], comp[v], w});
			edgs++;
			if (edgs == sz - 1) break;
		}
	}

	long long ans = 0;
	for (int bm = 1; bm < (1 << k); bm++) {
		dsu.clear(sz);
		g.clear(sz);

		for (int i = 0; i < k; i++) {
			if (!(bm & (1 << i))) continue;
			auto [u, v, w] = nedges[i];
			if (dsu.join(u, v)) {
				g.addEdge(u, v, INT_MAX);
			}
		}

		vector<Edge> unused;
		for (auto [u, v, w] : mn) {
			if (dsu.join(u, v)) {
				g.addEdge(u, v, 0);
			}
			else {
				unused.push_back({u, v, w});
			}
		}

		g.dfs(1, -1);
		for (auto [u, v, w] : unused) {
			if (g.d[u] < g.d[v])
				swap(u, v);

			while (g.d[u] > g.d[v]) {
				g.we[u] = min(g.we[u], w);
				u = g.par[u];
			}
		
			while (u != v) {
				g.we[u] = min(g.we[u], w);
				g.we[v] = min(g.we[v], w);
				u = g.par[u], v = g.par[v];
			}
		}

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

		ans = max(ans, can);
	}

	printf("%lld\n", ans);

	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d %d %d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   scanf("%d %d %d", &ai, &bi, &ci);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   scanf("%d %d", &xi, &yi);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
toll.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   scanf("%d", a + i);
      |   ~~~~~^~~~~~~~~~~~~
toll.cpp:58:13: warning: array subscript -1 is below array bounds of 'int [25]' [-Warray-bounds]
   58 |   d[v] = d[p] + 1;
      |          ~~~^
toll.cpp:41:13: note: while referencing 'Tree::d'
   41 |  int we[K], d[K], par[K];
      |             ^
toll.cpp:69:6: note: defined here 'g'
   69 | Tree g;
      |      ^

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 300 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 300 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 300 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 194 ms 7180 KB Output is correct
8 Correct 197 ms 7064 KB Output is correct
9 Correct 194 ms 7088 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 300 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 194 ms 7180 KB Output is correct
8 Correct 197 ms 7064 KB Output is correct
9 Correct 194 ms 7088 KB Output is correct
10 Correct 1359 ms 7076 KB Output is correct
11 Correct 1724 ms 11844 KB Output is correct
12 Correct 1695 ms 11940 KB Output is correct