Submission #1122849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122849		Skymagic	Training (IOI07_training)	C++20	100 / 100	10 ms	4680 KiB

training

/***********************
 * what    the   sigma *
 * stolen from Thunnus *
 ***********************/
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define lgm cin.tie(0)->sync_with_stdio(0);
#define be(x) x.begin(),x.end()
#define ve vector
#define ll long long
#define ld long double
#define db(x) cout << "Debug at " << x << endl;
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int, int>
#define tii tuple<int,int,int>
#define pll pair<ll,ll>
#define sz(x) (int)x.size()
#define pb push_back
const int mod = 1e9+7,maxn=5001,maxm=25001,maxk=10;
int n, m, sum;
pii par[maxn];
int jump[maxn][maxk+1];
vector<int> paths[maxn];
int deg[maxn],order[maxn],lvl[maxn],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 LCA(int a, int b) {
	if (lvl[a] < lvl[b]) swap(a, b);
    int dist=lvl[a]-lvl[b];
    for (int j = 0; j <= maxk; j++) {
		if (dist&(1<<j)) {
			a = jump[a][j];
		}
	}
	if (a == b) return a;
	for (int j = maxk; j >= 0; j--) {
		if (jump[a][j] != jump[b][j]) {
			a = jump[a][j];
			b = jump[b][j];
		}
	}
	return jump[a][0];
}
int dp[maxn][1<<maxk], 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;
		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;
			dp[lca][mask]=max(dp[lca][mask], cur + dp[lca][mask|mask1]);
		}
	}
}
signed main() {
	lgm;
	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 <= maxk; 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(be(edges));
	solve();
	cout << sum-dp[1][0] << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9