oj.uz

Submission #410791

# Submission time Handle Problem Language Result Execution time Memory
410791 2021-05-23T18:09:54 Z dongliu0426 Training (IOI07_training) C++17
100 / 100
 19 ms 4428 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][1 << 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] = mp(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) {
	if (d[i] > d[j])
		swap(i, 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 (x.c && (d[x.a] & 1) != (d[x.b] & 1))
			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 = 0; i < 1 << deg[x.lca]; ++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);
	}
	cout << (ans -= dp[0][0]) << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4428 KB Output is correct
2 Correct 7 ms 4388 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 844 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 4 ms 1484 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1996 KB Output is correct
2 Correct 6 ms 972 KB Output is correct
3 Correct 5 ms 1228 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 588 KB Output is correct
2 Correct 4 ms 1544 KB Output is correct
3 Correct 19 ms 4372 KB Output is correct
4 Correct 4 ms 1612 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1868 KB Output is correct
2 Correct 13 ms 4300 KB Output is correct
3 Correct 6 ms 1484 KB Output is correct
4 Correct 6 ms 1228 KB Output is correct