Submission #753687

#	Time	Username	Problem	Language	Result	Execution time	Memory
753687		lukameladze	Training (IOI07_training)	C++14	91 / 100	702 ms	8360 KiB

training

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int N = 1005, M = 5005;
int t,n,m,a[N],in[N],out[N],tin, dp[N][1025],id[N][N];
int par[N],lv[N];
vector <int> v[N];
void dfs(int a, int p) {
	in[a] = ++tin;
	par[a] = p;
	lv[a] = lv[p] + 1;
	for (int to : v[a]) {
		if (to == p) continue;
		dfs(to, a);
	}
	out[a] = tin;
}
int upper(int a, int b) {
	return (in[a] <= in[b] && out[a] >= out[b]);
}
int lca(int a, int b) {
	int cur = a;
	while (!upper(cur, b)) {
		cur = par[cur];
	}
	return cur;
}
int get(int a, int p) {
	int cur = a, lst = -1, ans = 0;
	while (cur != p) {
		if (lst == -1) ans += dp[cur][0];
		else ans += dp[cur][(1<<id[cur][lst])];
		lst = cur;
		cur = par[cur];
	}
	return ans;
}
vector <array <int, 3> > g[N];
int kth(int x, int k) {
	while (k--) {
		x = par[x];
	}
	return x;
}
void dfs1(int a, int p) {
	int cnt = 0;
	
	for (int to : v[a]) {
		if (to == p) continue;
		id[a][to] = cnt;
		cnt++;
		dfs1(to, a);
	}
	vector <array <int, 4> > pot;
	for (array <int, 3> edge : g[a]) {
		int x = edge[0], y = edge[1], z = edge[2];
		int msk = 0;
		if (a != x) {
			int getx = kth(x, lv[x] - lv[a] - 1);
			msk |= (1<<id[a][getx]);
		} 
 
		if (a != y) {
			int gety = kth(y, lv[y] - lv[a] - 1);
			msk |= (1<<id[a][gety]);
		}
 
		pot.pb({x, y, z, msk});
	}
	for (int msk = 0; msk < (1<<cnt); msk++) {
	    for (int to : v[a]){
	        if (to == p) continue;
	        if (!((1<<id[a][to])&msk)) dp[a][msk] += dp[to][0];
	    }
	}
	for (array <int, 4> edge : pot) {
		int x = edge[0], y = edge[1], z = edge[2], cur_mask = edge[3];
		for (int msk = (1<<cnt) - 1; msk >= 0; msk--) {
			if ((msk & cur_mask)) continue;
			int cur_pas = dp[a][msk | cur_mask]; // add(x -- y) wibo
			cur_pas += get(x, a) + get(y, a) + z;
			dp[a][msk] = max(dp[a][msk], cur_pas);
		}
		//cout<<a<<" "<<dp[a][0]<<" "<<dp[a][1]<<"\n";
	}
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	vector < array <int, 3 > > vec, vn;
	int sum = 0;
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		cin>>a>>b>>c;
		sum += c;
		if (c == 0) {
			v[a].pb(b);
			v[b].pb(a);
		} else {
			vec.pb({a, b, c});
		}
	}
	dfs(1, 0);
	for (array <int, 3> x : vec) {
		int a = x[0], b = x[1], c = x[2];
		int dist = lv[a] + lv[b] - 2 * lv[lca(a, b)];
		if (dist % 2 == 1) { // delete 
		} else vn.pb(x);
	}
	vec = vn;
	for (array <int, 3> x : vec) {
		int a = x[0], b = x[1], c = x[2];
		g[lca(a, b)].pb({a,b,c});
	}
	dfs1(1, 0);
	cout<<sum - dp[1][0]<<"\n";
}

Compilation message (stderr)

training.cpp:90:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   90 | main() {
      | ^~~~
training.cpp: In function 'int main()':
training.cpp:108:27: warning: unused variable 'c' [-Wunused-variable]
  108 |   int a = x[0], b = x[1], c = x[2];
      |                           ^

• 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: 0 / 9
• Subtask 11: 9 / 9