oj.uz

Submission #410770

# Submission time Handle Problem Language Result Execution time Memory
410770 2021-05-23T17:22:58 Z dongliu0426 Training (IOI07_training) C++17
0 / 100
 5 ms 460 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define f first
#define s second

const int N = 1000;
const int M = 10;

struct Road {
	int a, b, c, lca;
};

int n, m, deg[N], d[N], st[N], en[N], ti = 0, dp[N][M];
vector<int> adj[N];
pi pa[N];
vector<Road> roads;

void dfs(int i, int k) {
	st[i] = ++ti;
	for (int j : adj[i])
		if (j != k) {
			pa[j] = {i, 1 << deg[i]++};
			d[j] = d[i] ^ 1;
			dfs(j, i);
		}
	en[i] = ++ti;
}

bool anc(int i, int j) {
	return st[i] <= st[j] && en[i] >= en[j];
}

int lca(int i, int j) {
	while (!anc(i, j))
		i = pa[i].f;
	return i;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	
	cin >> n >> m;
	roads.rsz(m);
	int ans = 0;
	for (Road& x : roads) {
		cin >> x.a >> x.b >> x.c, --x.a, --x.b;
		ans += x.c;
		if (x.c == 0) {
			adj[x.a].pb(x.b);
			adj[x.b].pb(x.a);
		}
	}
	dfs(0, 0);
	for (Road& x : roads)
		x.lca = lca(x.a, x.b);
	sort(roads.begin(), roads.end(), [&](const Road &i, const Road &j) {
		return en[i.lca] < en[j.lca];
	});
	for (const Road& x : roads) {
		if (d[x.a] != d[x.b] || !x.c)
			continue;
		pi A, B; int sum = x.c;
		for (A = {x.a, 0}; A.f != x.lca; A = pa[A.f])
			sum += dp[A.f][A.s];
		for (B = {x.b, 0}; B.f != x.lca; B = pa[B.f])
			sum += dp[B.f][B.s];
		for (int i = (1 << deg[x.lca]) - 1; i >= 0; --i)
			if (!(i & A.s) && !(i & B.s))
				dp[x.lca][i] = max(dp[x.lca][i], dp[x.lca][i | A.s | B.s] + sum);
	}
	int maxrem = 0;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < 1 << deg[i]; ++j)
			maxrem = max(maxrem, dp[i][j]);
	ans -= maxrem;
	cout << ans << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 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 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

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