oj.uz

Submission #263190

# Submission time Handle Problem Language Result Execution time Memory
263190 2020-08-13T13:57:27 Z sjimed Training (IOI07_training) C++14
100 / 100
 50 ms 22392 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<int> List[1010];
vector<int> child[1010];
vector<pii> q[5010];
vector<ti> e;
int idx[1010][1010];
int c[1010];
int key[5010];
int d[1010];
int sp[1010][11];
ll ans = 0;

int dp[1100][1100];
int sum[5100];

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];
}

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;
		
		child[x].eb(i);
		idx[i][x] = idx[x][i] = c[x]++;
		
		dfs(i);
	}
}

void f(int x) {
	for(auto i : child[x]) {
		f(i);
	}

	for(auto i : List[x]) {
		for(auto j : q[i]) {
			sum[i] += dp[j.fi][j.se];
		}
	}

	for(int i=1; i < ( 1 << c[x] ); i++) {
		for(int j=0; j < c[x]; j++) {
			if(~i & (1<<j)) continue;

			int v = child[x][j];
			dp[x][i] = max(dp[x][i], dp[x][i ^ (1<<j)] + dp[v][(1<<c[v])-1]);
		}

		for(auto j : List[x]) {
			if( ~i & key[j] ) continue;

			dp[x][i] = max(dp[x][i], dp[x][i ^ key[j]] + sum[j] + get<2>(e[j]));
		}
	} 
}

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(int i=0; i<e.size(); i++) {
		int u, v, w;
		tie(u, v, w) = e[i];

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

		int l = lca(u, v);

		List[l].eb(i);

		if(l != u) q[i].eb(u, (1 << c[u]) - 1);
		if(l != v) q[i].eb(v, (1 << c[v]) - 1);

		for(u; u != l && sp[u][0] != l; u = sp[u][0]) {
			int p = sp[u][0];
			q[i].eb(p, (1 << c[p]) - 1 - (1 << idx[u][p]));
		}
		if(u != l) key[i] |= 1 << idx[u][l];

		for(u = v; u != l && sp[u][0] != l; u = sp[u][0]) {
			int p = sp[u][0];
			q[i].eb(p, (1 << c[p]) - 1 - (1 << idx[u][p]));
		}
		if(u != l) key[i] |= 1 << idx[u][l];
	}

	f(1);

	cout << ans - dp[1][(1<<c[1])-1];
}

Compilation message

training.cpp: In function 'int main()':
training.cpp:116:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |  for(int i=0; i<e.size(); i++) {
      |               ~^~~~~~~~~
training.cpp:129:7: warning: statement has no effect [-Wunused-value]
  129 |   for(u; u != l && sp[u][0] != l; u = sp[u][0]) {
      |       ^

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 17 ms 12288 KB Output is correct
2 Correct 16 ms 12800 KB Output is correct

Subtask #4
7.0 / 7.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 #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3200 KB Output is correct
2 Correct 6 ms 3232 KB Output is correct
3 Correct 8 ms 4352 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6656 KB Output is correct
2 Correct 11 ms 5248 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2944 KB Output is correct
2 Correct 7 ms 4864 KB Output is correct
3 Correct 42 ms 22392 KB Output is correct
4 Correct 11 ms 6016 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10496 KB Output is correct
2 Correct 50 ms 22392 KB Output is correct
3 Correct 21 ms 10368 KB Output is correct
4 Correct 13 ms 5504 KB Output is correct