oj.uz

Submission #899365

# Submission time Handle Problem Language Result Execution time Memory
899365 2024-01-05T22:09:40 Z Nonoze Training (IOI07_training) C++17
30 / 100
 19 ms 24668 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)>=child[s].size()) return 0;
	if (memo[s][mask]!=-1) return memo[s][mask];
	int ans=0;
	if (mask==0) {
		for (auto u: child[s]) {
			ans=max(ans, dp(u, 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);
			}
		}
	}
	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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 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 24412 KB Output is correct
2 Correct 14 ms 24668 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 24668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 24664 KB Output isn't correct
2 Halted 0 ms 0 KB -