oj.uz

Submission #262676

# Submission time Handle Problem Language Result Execution time Memory
262676 2020-08-13T06:48:40 Z 임성재(#5086) Training (IOI07_training) C++17
30 / 100
 140 ms 16120 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define pre(a) cout << fixed; cout.precision(a);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(v) (v).begin() (v).end()
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> ti;
const ll INF = 1e18;
const int inf = 1e9;

int n, m;
vector<int> G[1010];
vector<pll> g[1010];
vector<pair<pll, ll>> t[1010];
vector<ti> e;
int d[1010];
ll dp[1010][1010];
int sp[1010][11];
ll ans = 0;

int lca(int a, int b) {
	if(d[a] > d[b]) swap(a, b);

	for(int i=10; i>=0; i--) {
		if(d[b] - d[a] >= (1<<i)) b = sp[b][i];
	}

	if(a == b) return a;

	for(int i = 10; i>=0; i--) {
		if(sp[a][i] != sp[b][i]) {
			a = sp[a][i];
			b = sp[b][i];
		}
	}

	return sp[a][0];
}

int up(int a, int k) {
	for(int i=10; i>=0; i--) {
		if(k >= (1<<i)) 
			a = sp[a][i], k -= 1 << i;
	}

	return a;
}

void dfs(int x) {
	for(int i=1; i<=10; i++) {
		sp[x][i] = sp[sp[x][i-1]][i-1];
	}

	for(auto i : G[x]) {
		if(i == sp[x][0]) continue;

		sp[i][0] = x;
		d[i] = d[x] + 1;
		
		dfs(i);
	}
}

void f(int x) {
	ll mx[1010] = {};
	
	for(auto i : G[x]) {
		if(i == sp[x][0]) continue;

		f(i);
		mx[i] = dp[i][i];
	}

	for(auto i : g[x]) {
		int v = i.fi;
		int w = i.se;

		int u = up(v, d[v] - d[x] - 1);

		mx[u] = max(mx[u], dp[u][v] + w);
	}

	ll sum = 0;
	for(auto i : G[x]) {
		if(i == sp[x][0]) continue;

		sum += mx[i];
	}

	dp[x][x] = sum;

	for(int i=1; i<=n; i++) {
		if(i == x) continue;
		if(lca(i, x) != x) continue;

		int u = up(i, d[i] - d[x] - 1);

		dp[x][i] = dp[u][i] + sum - mx[u];

		dp[x][x] = max(dp[x][x], dp[x][i]);
	}

	for(auto i : t[x]) {
		int u = up(i.fi.fi, d[i.fi.fi] - d[x] - 1);
		int v = up(i.fi.se, d[i.fi.se] - d[x] - 1);

		dp[x][x] = max(dp[x][x], dp[u][i.fi.fi] + dp[v][i.fi.se] +  sum - mx[u] - mx[v] + i.se);
	}
}

int main() {
	fast;
	cin >> n >> m;

	for(int i=0; i<m; i++) {
		int u, v, w;
		cin >> u >> v >> w;

		ans += w;

		if(w == 0) G[u].eb(v), G[v].eb(u);
		else e.eb(u, v, w);
	}

	dfs(1);

	for(auto i : e) {
		int u, v, w;
		tie(u, v, w) = i;

		if(d[u] > d[v]) swap(u, v);
		if(d[u] % 2 != d[v] % 2) continue;

		int l = lca(u, v);

		if(u == l) g[u].eb(v, w);
		else t[l].eb(mp(u, v), w);
	}

	f(1);

	cout << ans - dp[1][1];
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 13816 KB Output is correct
2 Correct 128 ms 16120 KB Output is correct

Subtask #4
0 / 7.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

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