Submission #1000662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000662		BF001	Training (IOI07_training)	C++17	100 / 100	8 ms	4956 KiB

training

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

#define N 1005
#define int long long
#define fi first
#define se second
#define log 10

typedef pair<int, int> pi;

int n, dp[N][1 << 10], dep[N], tout[N], m, sum = 0, tin[N], tim, cnt[N], jmp[15][N];
vector<int> adj[N];
pi par[N];

struct iii{
	int u, v, w;
};

struct ii
{
	int u, v, w, lca;
	bool operator < (ii& o){
		return tout[lca] < tout[o.lca];
	}
};

vector<iii> vec;
vector<ii> eg;

void dfs(int u, int p){
	tin[u] = ++tim;
	for (auto x : adj[u]){
		if (x == p) continue;
		par[x] = {u, (1 << cnt[u])};
		jmp[0][x] = u;
		cnt[u]++;
		dep[x] = dep[u] + 1;
		dfs(x, u);
	}
	tout[u] = ++tim;
}

bool in(int u, int v){
	return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}

int getlca(int u, int v){
	if (in(u, v)) return u;
	if (in(v, u)) return v;
	for (int k = log; k >= 0; k--){
		if (jmp[k][u] && !in(jmp[k][u], v)) u = jmp[k][u];
	}
	return jmp[0][u];
}

void dpp(){
	for (auto x : eg){
		int d1 = (dep[x.u] & 1);
   		int d2 = (dep[x.v] & 1);
   		if (d1 != d2 && x.w != 0) continue;
		int a  = x.u, msk1 = 0, b = x.v, msk2 = 0;
		int sum = x.w;
		for (msk1 = 0; a != x.lca; msk1 = par[a].se, a = par[a].fi){
			sum += dp[a][msk1];
		}
		for (msk2 = 0; b != x.lca; msk2 = par[b].se, b = par[b].fi){
			sum += dp[b][msk2];
		}
		msk1 |= msk2;
		for (int msk = (1 << cnt[x.lca]) - 1; msk >= 0; msk--){
			if (msk & msk1) continue;
			dp[x.lca][msk] = max(dp[x.lca][msk], sum + dp[x.lca][msk | msk1]);
		}
	}
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
      
   	cin >> n >> m;
   	for (int i = 1; i <= m; i++){
   		int u, v, w;
   		cin >> u >> v >> w;
   		if (w == 0){
   			adj[u].push_back(v);
   			adj[v].push_back(u);
   		}
   		sum += w;
   		vec.push_back({u, v, w});
   	}  

   	par[1] = {1, 0};
   	dfs(1, 0); 
   	for (int k = 1; k <= log; k++){
   		for (int i = 1; i <= n; i++) jmp[k][i] = jmp[k - 1][jmp[k - 1][i]];
   	}

   	for (auto x : vec){
   		int d1 = (dep[x.u] & 1);
   		int d2 = (dep[x.v] & 1);
   		if (d1 != d2 && x.w != 0) continue;
   		int lca = getlca(x.u, x.v);
   		eg.push_back({x.u, x.v, x.w, lca});
   	}

   	sort(eg.begin(), eg.end());
   	dpp();

   	cout << sum - dp[1][0];

    return 0;
}     

• 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