oj.uz

Submission #977687

# Submission time Handle Problem Language Result Execution time Memory
977687 2024-05-08T09:15:40 Z phoenix0423 Training (IOI07_training) C++17
100 / 100
 11 ms 4700 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<double, ll> pdl;
typedef pair<ll, double> pld;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// #pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back 
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 1e3 + 5;
const double INF = 1e18;
const int N = 998244353;
vector<int> adj[maxn];
int dep[maxn], succ[maxn][10], rk[maxn];
int dp[maxn][1 << 10];

struct edge{
	int u, v, w;
	edge(){}
	edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w){}
};
vector<edge> e, st[maxn];

void dfs(int pos, int prev){
	if(prev != pos) adj[pos].erase(find(adj[pos].begin(), adj[pos].end(), prev));
	succ[pos][0] = prev;
	for(int i = 1; i < 10; i++) succ[pos][i] = succ[succ[pos][i - 1]][i - 1];
	for(int i = 0; i < adj[pos].size(); i++){
		int x = adj[pos][i];
		rk[x] = i;
		dep[x] = dep[pos] + 1;
		dfs(x, pos);
	}
}

int lift(int b, int steps){
	while(steps) b = succ[b][__builtin_ctz(steps)], steps -= lowbit(steps);
	return b;
}

edge fd(int a, int b, int lc, int w){
	int ans = w;
	int lst = -1;
	while(a != lc){
		if(lst == -1) ans += dp[a][(1 << adj[a].size()) - 1];
		else ans += dp[a][((1 << adj[a].size()) - 1) ^ (1 << rk[lst])];
		lst = a;
		if(succ[a][0] == lc) break;
		a = succ[a][0];
	}
	lst = -1;
	while(b != lc){
		if(lst == -1) ans += dp[b][(1 << adj[b].size()) - 1];
		else ans += dp[b][((1 << adj[b].size()) - 1) ^ (1 << rk[lst])];
		lst = b;
		if(succ[b][0] == lc) break;
		b = succ[b][0];
	}
	if(a == lc) swap(a, b);
	a = rk[a], b = (b == lc ? -1 : rk[b]);
	return edge(a, b, ans);
}

void dfs2(int pos){
	for(auto x : adj[pos]){
		dfs2(x);
		for(int mask = (1 << adj[pos].size()) - 1; mask >= 0; mask--){
			if(mask & (1 << rk[x])) continue;
			dp[pos][mask | (1 << rk[x])] = max(dp[pos][mask | (1 << rk[x])], dp[pos][mask] + dp[x][(1 << adj[x].size()) - 1]);
		}
	}
	for(auto [u, v, w] : st[pos]){
		auto [a, b, c] = fd(u, v, pos, w);
		int m = (1 << a) + (b >= 0 ? (1 << b) : 0);
		for(int mask = (1 << adj[pos].size()) - 1; mask >= 0; mask--){
			if(mask & m) continue;
			dp[pos][mask | m] = max(dp[pos][mask | m], dp[pos][mask] + c);
		}
	}
	for(int mask = 0; mask < (1 << adj[pos].size()); mask++){
		for(int i = 0 ; i < adj[pos].size(); i++){
			if(mask & (1 << i)) dp[pos][mask] = max(dp[pos][mask], dp[pos][mask ^ (1 << i)]);
		}
	}
}

int lca(int a, int b){
	if(dep[a] > dep[b]) swap(a, b);
	b = lift(b, dep[b] - dep[a]);
	if(a == b) return a;
	for(int i = 9; i >= 0; i--){
		if(succ[a][i] != succ[b][i]) a = succ[a][i], b = succ[b][i];
	}
	return succ[a][0]; 
}

signed main(void){
	fastio;
	int n, m;
	cin>>n>>m;
	int tl = 0;
	for(int i = 0; i < m; i++){
		int a, b, w;
		cin>>a>>b>>w;
		a--, b--;
		tl += w;
		if(!w) adj[a].pb(b), adj[b].pb(a);
		else e.eb(edge(a, b, w));
	}
	dfs(0, 0);
	for(auto [u, v, w] : e){
		int lc = lca(u, v);
		if((dep[u] + dep[v] - 2 * dep[lc]) % 2) continue;
		st[lc].eb(edge(u, v, w));
	}
	dfs2(0);
	cout<<tl - dp[0][(1 << adj[0].size()) - 1]<<"\n";
}

Compilation message

training.cpp: In function 'void dfs(long long int, long long int)':
training.cpp:33:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 0; i < adj[pos].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~
training.cpp: In function 'void dfs2(long long int)':
training.cpp:86:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i = 0 ; i < adj[pos].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4700 KB Output is correct
2 Correct 5 ms 4696 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.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 #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1112 KB Output is correct
2 Correct 2 ms 1116 KB Output is correct
3 Correct 3 ms 1764 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 4 ms 1372 KB Output is correct
3 Correct 3 ms 1628 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1116 KB Output is correct
2 Correct 2 ms 1884 KB Output is correct
3 Correct 9 ms 4696 KB Output is correct
4 Correct 2 ms 1880 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2396 KB Output is correct
2 Correct 11 ms 4700 KB Output is correct
3 Correct 5 ms 1992 KB Output is correct
4 Correct 4 ms 1824 KB Output is correct