oj.uz

Submission #543030

# Submission time Handle Problem Language Result Execution time Memory
543030 2022-03-28T21:45:59 Z sidon Training (IOI07_training) C++17
100 / 100
 60 ms 4556 KB 
#include <bits/stdc++.h>
using namespace std;
#define maxim(X, Y) (X = max(X, Y))

const int MXN = 1e3, Z = 5e3;

int N, M, A[Z], B[Z], C[Z], p[MXN], d[MXN];
int cd[Z];
vector<int> g[MXN], h[MXN];

void init(int u) {
	for(const int &v : g[u]) {
		for(int &w : g[v]) if(u == w) swap(w, g[v].back());
		g[v].pop_back();
		p[v] = u;
		d[v] = d[u] + 1;
		init(v);
	}
}

int lca(int u, int v) {
	for(; u != v; d[u] > d[v] ? u = p[u] : v = p[v]);
	return u;
}

int getIdx(int u, int v) {
	for(int i = 0; 1; ++i) if(g[u][i] == v) return i;
}

const int NB = 1023;
int dp[MXN][1<<10];

void dfs(int u) {
	for(const int &v : g[u]) if(v != p[u]) dfs(v);
	for(const int &i : h[u]) {
		int cur {};
		for(int v : {A[i], B[i]}) if(u != v) {
			cur += dp[v][NB];
			int w = v; v = p[v];
			for(; u != v; w = v, v = p[v])
				cur += dp[v][NB^(1<<getIdx(v, w))];
			cd[i] ^= 1<<getIdx(u, w);
		}
		maxim(dp[u][cd[i]], cur + C[i]);
	}

	for(int i = 1; i <= NB; ++i) {
		for(int j = 0; j < 10; ++j) if(i & (1<<j))
			maxim(dp[u][i], dp[u][i ^ (1<<j)] + (j < int(size(g[u])) ? dp[g[u][j]][NB] : 0));

		for(const int &j : h[u]) if((i & cd[j]) == cd[j])
			maxim(dp[u][i], dp[u][i ^ cd[j]] + dp[u][cd[j]]);
	}
}

int main() {
	cin >> N >> M;
	for(int i = 0; i < M; ++i) {
		cin >> A[i] >> B[i] >> C[i];
		--A[i], --B[i];
		if(!C[i]) {
			g[A[i]].push_back(B[i]);
			g[B[i]].push_back(A[i]);
		}
	}
	init(0);

	for(int i = 0; i < M; ++i) if(C[i]) {
		if(!((d[A[i]] ^ d[B[i]]) & 1))
			h[lca(A[i], B[i])].push_back(i);
	}

	dfs(0);

	cout << accumulate(C, C + M, 0) - dp[0][NB];
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4500 KB Output is correct
2 Correct 48 ms 4552 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 724 KB Output is correct
2 Correct 6 ms 772 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1508 KB Output is correct
2 Correct 16 ms 1524 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2420 KB Output is correct
2 Correct 29 ms 2380 KB Output is correct
3 Correct 27 ms 2448 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 4432 KB Output is correct
2 Correct 54 ms 4448 KB Output is correct
3 Correct 59 ms 4536 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2312 KB Output is correct
2 Correct 29 ms 2408 KB Output is correct
3 Correct 53 ms 4452 KB Output is correct
4 Correct 27 ms 2444 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 4448 KB Output is correct
2 Correct 52 ms 4556 KB Output is correct
3 Correct 60 ms 4452 KB Output is correct
4 Correct 59 ms 4524 KB Output is correct