oj.uz

Submission #899423

# Submission time Handle Problem Language Result Execution time Memory
899423 2024-01-06T07:02:55 Z Nonoze Training (IOI07_training) C++17
100 / 100
 34 ms 24848 KB 
#include <bits/stdc++.h>

#define int long long
#define sz(x) (int)(x.size())

using namespace std;

const int LOG=12;

int n, m;

//LSONE

int LSOne(int i) {
	return i&(-i);
}


//LCA
vector<vector<int>> child;
vector<vector<int>> up;
vector<int> depth;

void dfs(int s, int last=-1) {
	for (auto u: child[s]) {
		if (u==last) continue;
		depth[u]=depth[s]+1;

		up[u][0]=s;
		for (int i=1; i<LOG; i++) {
			up[u][i]=up[ up[u][i-1] ][ i-1 ];
		}

		dfs(u, s);
	}
}

int getlca(int a, int b) {
	if (a==b) return a;
	if (depth[a] < depth[b]) swap(a, b);
	int k = depth[a] - depth[b];
	for (int j = LOG-1; j >= 0; j--) {
		if (k & (1<<j)) {
			a=up[a][j];
		}
	}
	if (a==b) return a;

	for (int j = LOG-1; j >= 0; j--) {
		if (up[a][j] != up[b][j]) {
			a=up[a][j];
			b=up[b][j];
		}
	}
	return up[a][0];
}

//DP
vector<vector<int>> memo;
vector<vector<pair<pair<int, int>, int>>> adj;
vector<vector<int>> val;
vector<vector<int>> memo2;

int dp(int s, int mask) {
	if (__builtin_popcount(mask)>=sz(child[s])) return 0;
	if (memo[s][mask]!=-1) return memo[s][mask];
	int ans=0;
	int temp=mask, lst=0;
	while (temp>0) {
		int lsone=LSOne(temp);
		int act=log2(lsone);
		for (int i=lst; i<act; i++) ans+=dp(child[s][i], 0);
		lst=act+1;
		temp-=lsone;
	}
	for (int i=lst; i<sz(child[s]); i++) ans+=dp(child[s][i], 0);

	for (auto u: adj[s]) {
		int a=u.first.first, b=u.first.second, c=u.second;
		if (mask&val[a][b]) continue;
		if (memo2[a][b]!=-1) {
			int sum=memo2[a][b];
			ans=max(ans, sum+dp(s, (mask|val[a][b])));
			continue;
		}
		int aa=a, bb=b;
		int sum=c;
		int prec=-1;
		while (a!=s) {
			int bitmask=0;
			for (int i=0; i<sz(child[a]); i++) {
				if (child[a][i]==prec) {
					bitmask+=(1<<i);
				}
			}
			sum+=dp(a, bitmask);
			prec=a;
			a=up[a][0];
		}

		prec=-1;
		while (b!=s) {
			int bitmask=0;
			for (int i=0; i<sz(child[b]); i++) {
				if (child[b][i]==prec) {
					bitmask+=(1<<i);
				}
			}
			sum+=dp(b, bitmask);
			prec=b;
			b=up[b][0];
		}
		memo2[aa][bb]=sum;
		ans=max(ans, sum+dp(s, (mask|val[aa][bb])));
	}
	return memo[s][mask]=ans;
}

void solve() {
	cin >> n >> m;
	memo.clear();
	memo.resize(n, vector<int>(1<<10, -1));
	memo2.clear();
	memo2.resize(n, vector<int>(n, -1));
	val.clear();
	val.resize(n, vector<int>(n));
	adj.clear();
	adj.resize(n);
	child.clear();
	child.resize(n);
	up.clear();
	up.resize(n, vector<int>(LOG));
	depth.clear();
	depth.resize(n);
	vector<pair<pair<int, int>, int>> temp;
	vector<int> vaut(n+5);
	for (int i=0; i<m; i++) {
		int u, v, c; cin >> u >> v >> c;
		u--, v--;
		if (c==0) {
			child[u].push_back(v);
			child[v].push_back(u);
		} else {
			temp.push_back({{u, v}, c});
		}
	}
	depth[0]=0;
	dfs(0);
	for (int s=0; s<n; s++) {
		for (int i=0; i<sz(child[s]); i++) {
			auto u=child[s][i];
			if (u==up[s][0]) {
				child[s].erase(child[s].begin()+i);
				break;
			}
		}
	}
	int ans=0;
	for (auto tempp: temp) {
		int u=tempp.first.first, v=tempp.first.second;
		int c=tempp.second;
		int lca=getlca(u, v);
		if (u!=v && (depth[u]+depth[v]-2*depth[lca])%2==0) {
			adj[lca].push_back({{u, v}, c});
			val[u][v]=0;
			for (int j=0; j<sz(child[lca]); j++) {
				auto s=child[lca][j];
				if (getlca(s, u)==s || getlca(s, v)==s) {
					val[u][v]+=(1<<j);
				}
			}
		}
		ans+=c;
	}
	cout << ans-dp(0, 0) << endl;
	return;
}


signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;// cin >> tt;
	while(tt--) solve();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24452 KB Output is correct
2 Correct 15 ms 24668 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 712 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8540 KB Output is correct
2 Correct 5 ms 8656 KB Output is correct
3 Correct 10 ms 8400 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24668 KB Output is correct
2 Correct 23 ms 24676 KB Output is correct
3 Correct 14 ms 24528 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8796 KB Output is correct
2 Correct 6 ms 8536 KB Output is correct
3 Correct 34 ms 24848 KB Output is correct
4 Correct 7 ms 8540 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24664 KB Output is correct
2 Correct 30 ms 24668 KB Output is correct
3 Correct 19 ms 24804 KB Output is correct
4 Correct 19 ms 24664 KB Output is correct