제출 #1142307

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142307		am_aadvik	Election Campaign (JOI15_election_campaign)	C++20	10 / 100	469 ms	327680 KiB

election_campaign

#include <iostream>
#include<cstring>
#include<vector>
using namespace std;

vector<int> g[100005];
bool ok[20][20];
int done[100005];

bool dfs(int node, int par, int t) {
	done[node]++;
	if (node == t) return 1;
	for (auto x : g[node])
		if (x != par)
			if (dfs(x, node, t)) return 1;
	done[node]--;
	return 0;
}

int main()
{
	int n; cin >> n;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	int m; cin >> m;
	vector<pair<int, int>> q(m);
	vector<int> c(m);
	for (int i = 0; i < m; ++i)
		cin >> q[i].first >> q[i].second >> c[i];

	for(int i = 0; i < m; ++i)
		for (int j = i + 1; j < m; ++j){
			dfs(q[i].first, -1, q[i].second);
			dfs(q[j].first, -1, q[j].second);
			bool y = 1;
			for (int i = 1; i <= n; ++i)
				if (done[i] > 1) y = 0;
			ok[i][j] = ok[j][i] = y;
			memset(done, 0, sizeof(done));
		}

	int ans = 0;
	for (int i = 0; i < (1 << m); ++i) {
		vector<int> a;
		for (int j = 0; j < m; ++j)
			if (i & (1 << j)) a.push_back(j);

		bool y = 1;
		for (int x = 0; x < a.size(); ++x)
			for (int j = x + 1; j < a.size(); ++j)
				if (!ok[a[x]][a[j]]) y = 0;
		if (!y) continue;

		int cur = 0;
		for (auto x : a) cur += c[x];
		ans = max(ans, cur);
	}
	cout << ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40