Submission #548499

#	Time	Username	Problem	Language	Result	Execution time	Memory
548499		Arinoor	Training (IOI07_training)	C++17	30 / 100	38 ms	4668 KiB

training

#include <bits/stdc++.h>
using namespace std;

#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define all(x)			x.begin(), x.end()
#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define bug(str, x)			cerr << str << " : " << x << '\n'

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
const int maxlg = 10;
const int inf = 1e9 + 10;
const int mod = 1e9 + 7;

int par[maxn][maxlg], h[maxn];
ll dp[maxn][1 << maxlg], val[maxn];
vector<int> G[maxn];
vector<pair<pii, int>> edge;
vector<pair<int, pii>> Q[maxn];

int get_par(int v, int h){
	if(h < 0)
		return v;
	for(int i = 0; i < maxlg; i ++)
		if(h >> i & 1)
			v = par[v][i];
	return v;
}

int lca(int v, int u){
	if(h[v] < h[u])
		swap(u, v);
	v = get_par(v, h[v] - h[u]);
	if(v == u)
		return v;
	for(int i = maxlg - 1; ~i; i --)
		if(par[v][i] != par[u][i]){
			v = par[v][i];
			u = par[u][i];
		}
	return par[v][0];
}

void dfs(int v, int p = 0){
	par[v][0] = p;
	for(int i = 1; i < maxlg and par[v][i - 1]; i ++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	for(int u : G[v])
		if(u != p){
			h[u] = h[v] + 1;
			dfs(u, v);
		}
}

int find(int v){
	return lower_bound(all(G[par[v][0]]), v) - G[par[v][0]].begin();
}

void DFS(int rt, int v){
	int p = par[v][0];
	if(v == rt or p == rt)
		val[v] = 0;
	else{
		val[v] = dp[v][0] + val[p] - dp[p][0];
		val[v] += dp[p][1 << find(v)];
	}
	for(int u : G[v])
		if(u != p)
			DFS(rt, u);
}

void Dfs(int v){
	for(int u : G[v])
		if(u != par[v][0])
			Dfs(u);
	DFS(v, v);
	int sz = G[v].size();
	for(int msk = 0; msk < 1 << sz; msk ++){
		ll sum = 0;
		for(int i = 0; i < sz; i ++)
			if(G[v][i] != par[v][0] and !(msk >> i & 1))
				sum += dp[G[v][i]][0];
		dp[v][msk] = sum;
		for(auto e : Q[v]){
			int u1 = edge[e.fi].fi.fi;
			int v1 = edge[e.fi].fi.se;
			if((e.se.fi == v or !((msk >> find(e.se.fi)) & 1)) and (e.se.se == v or !((msk >> find(e.se.se)) & 1)))
				dp[v][msk] = max(dp[v][msk], edge[e.fi].se + sum + val[u1] + val[v1]);
		}
	}
}

int main(){
	ios;
	int n, m;
	cin >> n >> m;
	ll sum = 0;
	for(int i = 0; i < m; i ++){
		int u, v, w;
		cin >> u >> v >> w;
		if(!w){
			G[u].pb(v);
			G[v].pb(u);
		}
		edge.pb(mp(mp(v, u), w));
		sum += w;
	}
	for(int i = 1; i <= n; i ++)
		sort(all(G[i]));
	dfs(1);
	for(int i = 0; i < m; i ++){
		if(!edge[i].se)
			continue;
		int v = edge[i].fi.fi;
		int u = edge[i].fi.se;
		if((h[v] + h[u]) % 2 == 0){
			int w = lca(u, v);
			Q[w].pb(mp(i, mp(get_par(v, h[v] - h[w] - 1), get_par(u, h[u] - h[w] - 1))));
		}
	}
	Dfs(1);
	cout << sum - dp[1][0] << '\n';
}

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