oj.uz

Submission #32319

# Submission time Handle Problem Language Result Execution time Memory
32319 2017-10-08T20:22:16 Z minimario Toll (APIO13_toll) C++14
100 / 100
 1866 ms 20340 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX = 300005;
typedef pair<int, int> pii;
typedef long long ll;
#define f first
#define s second

int id[MAX], sz[MAX];
void init(int n) {
	for (int i=0; i<=n; i++) {
		id[i] = i; 
		sz[i] = 1;
	}
}
int root(int u) {
	while (u != id[u]) { 
		id[u] = id[id[u]];
		u = id[u];
	}
	return u;
}
void join(int u, int v) {
	u = root(u); v = root(v);
	if (sz[u] < sz[v]) {
		swap(u, v);
	}
	id[v] = u;
	sz[u] += sz[v];
}


int map_to_comp[MAX], comp[MAX];

vector<int> g[25];
int p[25], d[25];
ll ppl_comp[25], ppl[25];

void dfs(int u, int par = -1, int dist = 0) {
	d[u] = dist; p[u] = par;
	for (int i : g[u]) {
		if (i == par) { continue; }
		dfs(i, u, dist+1);
		ppl[u] += ppl[i];
	}
}

int ct[25];
void lca(int u, int v, int val) {
	while (u != v) {
		if (d[u] > d[v]) {
			ct[u] = min(ct[u], val);
			u = p[u];
		}
		else {
			ct[v] = min(ct[v], val);
			v = p[v];
		}
	}
}

int ppl0[MAX];

int main() {
	int n, m, k; scanf("%d %d %d", &n, &m, &k);
	vector<pair<int, pii> > e0, mst, mst2;
	for (int i=0; i<m; i++) {
		int u, v, w; scanf("%d %d %d", &u, &v, &w);
		e0.push_back({w, {u, v}});
	}
	// find the MST
	sort(e0.begin(), e0.end());
	init(n);
	for (auto i : e0) {
		int u = root(i.s.f);
		int v = root(i.s.s);
		if (u != v) {
			join(u, v);
			mst.push_back(i);
		}
	}

	// find the new MST with k edges
	vector<pii> new_edges;
	init(n);
	for (int i=0; i<k; i++) {
		int u, v; scanf("%d %d", &u, &v);
		new_edges.push_back({u, v});
		u = root(u); v = root(v);
		if (u != v) { join(u, v); }
	}
	for (auto i : e0) {
		int u = root(i.s.f);
		int v = root(i.s.s);
		if (u != v) {
			join(u, v);
			mst2.push_back(i);
		}
	}

	for (int i=1; i<=n; i++) {
		scanf("%d", &ppl0[i]);
	}

	// find the components
	init(n);
	for (auto i : mst2) {
		int u = root(i.s.f);
		int v = root(i.s.s);
		join(u, v);
	}
	set<int> cc;
	for (int i=1; i<=n; i++) {
		cc.insert(root(i));
	}
	int cp = 0;
	for (int i : cc) {
		map_to_comp[i] = cp++;
	}
	for (int i=1; i<=n; i++) {
		comp[i] = map_to_comp[root(i)];
		ppl_comp[comp[i]] += (ll) ppl0[i];
	}

	vector<pair<int, pii> > diff; // contains the edges that will be used (with the compressed vertices)
	bool taken[1000005];
	for (auto i : mst2) {
		taken[i.f] = true;
	}
	for (auto i : mst) {
		if (!taken[i.f]) { diff.push_back({i.f, {comp[i.s.f], comp[i.s.s]}}); }
	}

	ll maxi = -1;
	for (int i=0; i<(1<<k); i++) {
		init(25);
		for (int j=0; j<25; j++) {
			p[j] = d[j] = 0;
			ct[j] = 1000005;
			ppl[j] = ppl_comp[j];
			g[j].clear();
		}
		bool cycle = false;
		for (int j=0; j<k; j++) {
			if (i&(1<<j)) {
				int u = comp[new_edges[j].f];
				int v = comp[new_edges[j].s];
				if (root(u) == root(v)) { cycle = true; }
				join(u, v);
				g[u].push_back(v);
				g[v].push_back(u);
			}
		}

		if (cycle) { continue; }
		vector<pair<int, pii> > upd_edges;
		for (auto i : diff) {
			int u = i.s.f; int v = i.s.s;
			if (root(u) != root(v)) {
				join(u, v);
				g[u].push_back(v);
				g[v].push_back(u);
			}
			else {
				upd_edges.push_back(i);
			}
		}
		dfs(comp[1]);
		for (auto i : upd_edges) {
			lca(i.s.f, i.s.s, i.f);
		}
		ll profit = 0;
		for (int j=0; j<k; j++) {
			if (i&(1<<j)) {
				int u = comp[new_edges[j].f];
				int v = comp[new_edges[j].s];
				if (d[u] > d[v]) { swap(u, v); }
				profit += ppl[v] * ct[v];
			}
		}
		maxi = max(maxi, profit);
	}
	printf("%lld\n", maxi);
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:66:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m, k; scanf("%d %d %d", &n, &m, &k);
                                            ^
toll.cpp:69:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, w; scanf("%d %d %d", &u, &v, &w);
                                             ^
toll.cpp:88:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d %d", &u, &v);
                                   ^
toll.cpp:103:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &ppl0[i]);
                        ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8740 KB Output is correct
2 Correct 0 ms 8740 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8740 KB Output is correct
2 Correct 0 ms 8740 KB Output is correct
3 Correct 0 ms 8736 KB Output is correct
4 Correct 0 ms 8736 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8740 KB Output is correct
2 Correct 0 ms 8740 KB Output is correct
3 Correct 0 ms 8736 KB Output is correct
4 Correct 0 ms 8736 KB Output is correct
5 Correct 3 ms 8912 KB Output is correct
6 Correct 3 ms 8908 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8740 KB Output is correct
2 Correct 0 ms 8740 KB Output is correct
3 Correct 0 ms 8736 KB Output is correct
4 Correct 0 ms 8736 KB Output is correct
5 Correct 3 ms 8912 KB Output is correct
6 Correct 3 ms 8908 KB Output is correct
7 Correct 249 ms 20340 KB Output is correct
8 Correct 236 ms 20340 KB Output is correct
9 Correct 226 ms 20340 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8740 KB Output is correct
2 Correct 0 ms 8740 KB Output is correct
3 Correct 0 ms 8736 KB Output is correct
4 Correct 0 ms 8736 KB Output is correct
5 Correct 3 ms 8912 KB Output is correct
6 Correct 3 ms 8908 KB Output is correct
7 Correct 249 ms 20340 KB Output is correct
8 Correct 236 ms 20340 KB Output is correct
9 Correct 226 ms 20340 KB Output is correct
10 Correct 1573 ms 20340 KB Output is correct
11 Correct 1866 ms 20340 KB Output is correct
12 Correct 1833 ms 20336 KB Output is correct