제출 #32319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32319		minimario	통행료 (APIO13_toll)	C++14	100 / 100	1866 ms	20340 KiB

toll

#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);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22