oj.uz

답안 #507839

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
507839 2022-01-13T04:02:21 Z 8e7 Training (IOI07_training) C++17
100 / 100
 34 ms 27484 KB 
//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 1005
#define maxc 10
#define maxm 5005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn], pnt[maxn], path[maxn];
pii ed[maxm], chi[maxm];
int w[maxm], pa[maxn], dep[maxn];
void dfs(int n, int par, int d) {
	dep[n] = d;
	pa[n] = par;
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n, d + 1);
		}
	}	
}
int ans = 0;
int tot, dp[maxn][maxm], id[maxn], best[maxn];
void solve(int n, int par) {
	int d = 0, sum = 0;
	for (int v:adj[n]) {
		if (v != par) {
			solve(v, n);
			sum += best[v];
			id[v] = d++;
		}
	}
	for (int i:pnt[n]) chi[i] = {0, 0};
	for (int v:adj[n]) {
		for (int j:path[v]) {
			if (!chi[j].ff) chi[j].ff = v;	
			else chi[j].ss = v;
		}
	}
	vector<int> bit(1<<d, sum);
	for (int i:pnt[n]) {
		auto [u, v] = chi[i];
		int se = 0, val = 0;
		if (u) se += 1<<id[u], val += dp[u][i] - best[u];
		if (v) se += 1<<id[v], val += dp[v][i] - best[v];
		//debug(i, chi[i].ff, chi[i].ss, se,val);
		for (int j = 0;j < (1<<d);j++) {
			if ((j & se) == 0) {
				bit[j | se] = max(bit[j | se], bit[j] + w[i] + val);
			}	
		}	
	}
	for (int i = 1;i < (1<<d);i++) {
		for (int j = 0;j < d;j++) {
			if (i & (1<<j)) bit[i] = max(bit[i], bit[i ^ (1<<j)]);
		}
	}
	ans = max(ans, bit[(1<<d) - 1]);
	best[n] = bit[(1<<d) - 1];
	for (int i = 1;i <= tot;i++) dp[n][i] = best[n];
	for (int v:adj[n]) {
		if (v == par) continue;
		for (int i:path[v]) {
			dp[n][i] = bit[(1<<d) - 1 - (1<<id[v])] - best[v] + dp[v][i];
		}
	}
	//debug(n, best[n]);
	//pary(bit.begin(), bit.end());
	//debug(n, dp[n][7]);
}	
int main() {
	io
	int n, m;
	cin >> n >> m;
	tot = m;
	int tc = 0;
	for (int i = 1;i <= m;i++) {
		int u, v;
		cin >> u >> v >> w[i];
		tc += w[i];
		if (w[i] == 0) {
			adj[u].push_back(v);
			adj[v].push_back(u);	
		} else {
			ed[i] = {u, v};
		}
	}
	dfs(1, 0, 0);
	int even = 0;
	for (int i = 1;i <= m;i++) {
		if (w[i]) {
			auto [u, v] = ed[i];
			if (dep[u] < dep[v]) swap(u, v);
			int len = 0;
			while (dep[u] > dep[v]) len++, path[u].push_back(i), u = pa[u];
			while (u != v) {
				path[u].push_back(i), path[v].push_back(i);
				len += 2;
				u = pa[u], v = pa[v];
			}
			if (len % 2 == 0) pnt[u].push_back(i);	
			else even += w[i], tc -= w[i];
		}
	}
	/*
	for (int i = 1;i <= n;i++) {
		debug("path", i);
		pary(path[i].begin(), path[i].end());
		debug("pnt");
		pary(pnt[i].begin(), pnt[i].end());
	}
	*/
	solve(1, 0);
	//debug(tc, even, ans);
	cout << tc - ans + even << endl;
}
/*
9 12
1 2 0
1 3 0
3 4 0
3 5 0
5 6 0
5 7 0
5 8 0
8 9 0
7 8 3
6 8 5
2 6 4
4 9 6

7 10
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
1 5 3
2 6 5
3 5 2
5 7 7
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 6 ms 6988 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 20548 KB Output is correct
2 Correct 13 ms 20376 KB Output is correct
3 Correct 13 ms 20444 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 6348 KB Output is correct
2 Correct 7 ms 7952 KB Output is correct
3 Correct 31 ms 26984 KB Output is correct
4 Correct 8 ms 8492 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 22476 KB Output is correct
2 Correct 34 ms 27484 KB Output is correct
3 Correct 23 ms 22492 KB Output is correct
4 Correct 14 ms 20352 KB Output is correct