Submission #977687

#	Time	Username	Problem	Language	Result	Execution time	Memory
977687		phoenix0423	Training (IOI07_training)	C++17	100 / 100	11 ms	4700 KiB

training

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<double, ll> pdl;
typedef pair<ll, double> pld;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// #pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back 
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 1e3 + 5;
const double INF = 1e18;
const int N = 998244353;
vector<int> adj[maxn];
int dep[maxn], succ[maxn][10], rk[maxn];
int dp[maxn][1 << 10];

struct edge{
	int u, v, w;
	edge(){}
	edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w){}
};
vector<edge> e, st[maxn];

void dfs(int pos, int prev){
	if(prev != pos) adj[pos].erase(find(adj[pos].begin(), adj[pos].end(), prev));
	succ[pos][0] = prev;
	for(int i = 1; i < 10; i++) succ[pos][i] = succ[succ[pos][i - 1]][i - 1];
	for(int i = 0; i < adj[pos].size(); i++){
		int x = adj[pos][i];
		rk[x] = i;
		dep[x] = dep[pos] + 1;
		dfs(x, pos);
	}
}

int lift(int b, int steps){
	while(steps) b = succ[b][__builtin_ctz(steps)], steps -= lowbit(steps);
	return b;
}

edge fd(int a, int b, int lc, int w){
	int ans = w;
	int lst = -1;
	while(a != lc){
		if(lst == -1) ans += dp[a][(1 << adj[a].size()) - 1];
		else ans += dp[a][((1 << adj[a].size()) - 1) ^ (1 << rk[lst])];
		lst = a;
		if(succ[a][0] == lc) break;
		a = succ[a][0];
	}
	lst = -1;
	while(b != lc){
		if(lst == -1) ans += dp[b][(1 << adj[b].size()) - 1];
		else ans += dp[b][((1 << adj[b].size()) - 1) ^ (1 << rk[lst])];
		lst = b;
		if(succ[b][0] == lc) break;
		b = succ[b][0];
	}
	if(a == lc) swap(a, b);
	a = rk[a], b = (b == lc ? -1 : rk[b]);
	return edge(a, b, ans);
}

void dfs2(int pos){
	for(auto x : adj[pos]){
		dfs2(x);
		for(int mask = (1 << adj[pos].size()) - 1; mask >= 0; mask--){
			if(mask & (1 << rk[x])) continue;
			dp[pos][mask | (1 << rk[x])] = max(dp[pos][mask | (1 << rk[x])], dp[pos][mask] + dp[x][(1 << adj[x].size()) - 1]);
		}
	}
	for(auto [u, v, w] : st[pos]){
		auto [a, b, c] = fd(u, v, pos, w);
		int m = (1 << a) + (b >= 0 ? (1 << b) : 0);
		for(int mask = (1 << adj[pos].size()) - 1; mask >= 0; mask--){
			if(mask & m) continue;
			dp[pos][mask | m] = max(dp[pos][mask | m], dp[pos][mask] + c);
		}
	}
	for(int mask = 0; mask < (1 << adj[pos].size()); mask++){
		for(int i = 0 ; i < adj[pos].size(); i++){
			if(mask & (1 << i)) dp[pos][mask] = max(dp[pos][mask], dp[pos][mask ^ (1 << i)]);
		}
	}
}

int lca(int a, int b){
	if(dep[a] > dep[b]) swap(a, b);
	b = lift(b, dep[b] - dep[a]);
	if(a == b) return a;
	for(int i = 9; i >= 0; i--){
		if(succ[a][i] != succ[b][i]) a = succ[a][i], b = succ[b][i];
	}
	return succ[a][0]; 
}

signed main(void){
	fastio;
	int n, m;
	cin>>n>>m;
	int tl = 0;
	for(int i = 0; i < m; i++){
		int a, b, w;
		cin>>a>>b>>w;
		a--, b--;
		tl += w;
		if(!w) adj[a].pb(b), adj[b].pb(a);
		else e.eb(edge(a, b, w));
	}
	dfs(0, 0);
	for(auto [u, v, w] : e){
		int lc = lca(u, v);
		if((dep[u] + dep[v] - 2 * dep[lc]) % 2) continue;
		st[lc].eb(edge(u, v, w));
	}
	dfs2(0);
	cout<<tl - dp[0][(1 << adj[0].size()) - 1]<<"\n";
}

Compilation message (stderr)

training.cpp: In function 'void dfs(long long int, long long int)':
training.cpp:33:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 0; i < adj[pos].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~
training.cpp: In function 'void dfs2(long long int)':
training.cpp:86:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i = 0 ; i < adj[pos].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~

• 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