oj.uz

Submission #1000662

# Submission time Handle Problem Language Result Execution time Memory
1000662 2024-06-18T06:33:43 Z BF001 Training (IOI07_training) C++17
100 / 100
 8 ms 4956 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4776 KB Output is correct
2 Correct 4 ms 4956 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 0 ms 348 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

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

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2500 KB Output is correct
2 Correct 6 ms 1736 KB Output is correct
3 Correct 4 ms 1988 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 3 ms 1884 KB Output is correct
3 Correct 8 ms 4804 KB Output is correct
4 Correct 2 ms 2044 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2640 KB Output is correct
2 Correct 7 ms 4792 KB Output is correct
3 Correct 5 ms 2140 KB Output is correct
4 Correct 4 ms 1988 KB Output is correct