oj.uz

답안 #507817

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
507817 2022-01-13T03:56:18 Z 8e7 Training (IOI07_training) C++17
0 / 100
 28 ms 22516 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]) {
		for (int i:path[v]) {
			dp[n][i] = bit[(1<<d) - 1 - (1<<id[v])] - best[v] + dp[v][i];
		}
	}
	//debug(n, best[n], dp[n][11]);
	//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
*/

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 19872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 7404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 20456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 6348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 22516 KB Output isn't correct
2 Halted 0 ms 0 KB -