oj.uz

답안 #592582

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
592582 2022-07-09T10:17:25 Z Mazaalai Training (IOI07_training) C++17
100 / 100
 15 ms 4584 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define chmax(a, b) a=max(a,b)
using namespace std;
using PII = pair <int, int>;
using VI = vector <int>;
const int N = 1001;
const int M = 5001;
const int K = 10;
int n, m, sum;
vector <int> paths[N];
int jump[N][K+1];
PII par[N];
int deg[N], order[N], lvl[N], ptr;
struct Edge {
	int a, b, c, lca;
	bool operator <(const Edge& x) const {
		return order[lca] < order[x.lca];
	}
};
vector <Edge> edges;
void dfs(int pos = 1, int p = 1) {
	jump[pos][0] = p;
	for (auto& el : paths[pos]) {
		if (el == p) continue;

		lvl[el] = lvl[pos]+1;
		par[el] = {pos, 1<<(deg[pos]++)};

		dfs(el, pos);
	}
	order[pos] = ptr++;
}
int Jump(int a, int b) {
	for (int j = 0; j <= K; j++) 
		if (b & (1<<j)) a = jump[a][j];
	return a;
}
int LCA(int a, int b) {
	if (lvl[a] < lvl[b]) swap(a, b);
	a = Jump(a, lvl[a]-lvl[b]);
	if (a == b) return a;
	for (int j = K; j >= 0; j--) {
		if (jump[a][j] != jump[b][j]) {
			a = jump[a][j];
			b = jump[b][j];
		}
	}
	return jump[a][0];
}
int dp[N][1<<K], mask1, mask2; 
void solve() {
	for (auto& edge : edges) {
		int a = edge.a, b = edge.b, cur = edge.c, lca = edge.lca;
		if (lvl[a]%2 != lvl[b]%2 && cur != 0) continue;

		// cutting edge a to b;
		// cout << a << ' ' << b << ": " << lca << ' ' << order[lca] << '\n';

		for (mask1 = 0; a != lca; tie(a, mask1) = par[a]) cur += dp[a][mask1];
		for (mask2 = 0; b != lca; tie(b, mask2) = par[b]) cur += dp[b][mask2];

		mask1 |= mask2;
		for (int mask = (1<<deg[lca])-1; mask >= 0; mask--) {
			if (mask & mask1) continue;
			chmax(dp[lca][mask], cur + dp[lca][mask|mask1]);
		}
	}
}
signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	// freopen("0.in", "r", stdin);
	// freopen("0.out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b, c; cin >> a >> b >> c;
		if (!c) {
			paths[a].pb(b);
			paths[b].pb(a);
		}
		sum += c;
		edges.pb({a, b, c, 0});
	}
	par[1] = {1, 0};
	dfs();
	for (int j = 1; j <= K; j++)
	for (int i = 1; i <= n; i++)
		jump[i][j] = jump[jump[i][j-1]][j-1];
	for (auto& edge : edges) {
		if (lvl[edge.a]%2 != lvl[edge.b]%2 && edge.c != 0) continue;
		edge.lca = LCA(edge.a, edge.b);
	}
	sort(ALL(edges));
	solve();
	cout << sum - dp[1][0] << "\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

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

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2132 KB Output is correct
2 Correct 4 ms 1140 KB Output is correct
3 Correct 4 ms 1492 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 1620 KB Output is correct
3 Correct 15 ms 4584 KB Output is correct
4 Correct 3 ms 1748 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2076 KB Output is correct
2 Correct 14 ms 4452 KB Output is correct
3 Correct 6 ms 1620 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct