oj.uz

Submission #753687

# Submission time Handle Problem Language Result Execution time Memory
753687 2023-06-05T17:12:42 Z lukameladze Training (IOI07_training) C++14
91 / 100
 300 ms 8360 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int N = 1005, M = 5005;
int t,n,m,a[N],in[N],out[N],tin, dp[N][1025],id[N][N];
int par[N],lv[N];
vector <int> v[N];
void dfs(int a, int p) {
	in[a] = ++tin;
	par[a] = p;
	lv[a] = lv[p] + 1;
	for (int to : v[a]) {
		if (to == p) continue;
		dfs(to, a);
	}
	out[a] = tin;
}
int upper(int a, int b) {
	return (in[a] <= in[b] && out[a] >= out[b]);
}
int lca(int a, int b) {
	int cur = a;
	while (!upper(cur, b)) {
		cur = par[cur];
	}
	return cur;
}
int get(int a, int p) {
	int cur = a, lst = -1, ans = 0;
	while (cur != p) {
		if (lst == -1) ans += dp[cur][0];
		else ans += dp[cur][(1<<id[cur][lst])];
		lst = cur;
		cur = par[cur];
	}
	return ans;
}
vector <array <int, 3> > g[N];
int kth(int x, int k) {
	while (k--) {
		x = par[x];
	}
	return x;
}
void dfs1(int a, int p) {
	int cnt = 0;
	
	for (int to : v[a]) {
		if (to == p) continue;
		id[a][to] = cnt;
		cnt++;
		dfs1(to, a);
	}
	vector <array <int, 4> > pot;
	for (array <int, 3> edge : g[a]) {
		int x = edge[0], y = edge[1], z = edge[2];
		int msk = 0;
		if (a != x) {
			int getx = kth(x, lv[x] - lv[a] - 1);
			msk |= (1<<id[a][getx]);
		} 
 
		if (a != y) {
			int gety = kth(y, lv[y] - lv[a] - 1);
			msk |= (1<<id[a][gety]);
		}
 
		pot.pb({x, y, z, msk});
	}
	for (int msk = 0; msk < (1<<cnt); msk++) {
	    for (int to : v[a]){
	        if (to == p) continue;
	        if (!((1<<id[a][to])&msk)) dp[a][msk] += dp[to][0];
	    }
	}
	for (array <int, 4> edge : pot) {
		int x = edge[0], y = edge[1], z = edge[2], cur_mask = edge[3];
		for (int msk = (1<<cnt) - 1; msk >= 0; msk--) {
			if ((msk & cur_mask)) continue;
			int cur_pas = dp[a][msk | cur_mask]; // add(x -- y) wibo
			cur_pas += get(x, a) + get(y, a) + z;
			dp[a][msk] = max(dp[a][msk], cur_pas);
		}
		//cout<<a<<" "<<dp[a][0]<<" "<<dp[a][1]<<"\n";
	}
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	vector < array <int, 3 > > vec, vn;
	int sum = 0;
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		cin>>a>>b>>c;
		sum += c;
		if (c == 0) {
			v[a].pb(b);
			v[b].pb(a);
		} else {
			vec.pb({a, b, c});
		}
	}
	dfs(1, 0);
	for (array <int, 3> x : vec) {
		int a = x[0], b = x[1], c = x[2];
		int dist = lv[a] + lv[b] - 2 * lv[lca(a, b)];
		if (dist % 2 == 1) { // delete 
		} else vn.pb(x);
	}
	vec = vn;
	for (array <int, 3> x : vec) {
		int a = x[0], b = x[1], c = x[2];
		g[lca(a, b)].pb({a,b,c});
	}
	dfs1(1, 0);
	cout<<sum - dp[1][0]<<"\n";
}

Compilation message

training.cpp:90:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   90 | main() {
      | ^~~~
training.cpp: In function 'int main()':
training.cpp:108:27: warning: unused variable 'c' [-Wunused-variable]
  108 |   int a = x[0], b = x[1], c = x[2];
      |                           ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7892 KB Output is correct
2 Correct 8 ms 7980 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1620 KB Output is correct
2 Correct 2 ms 1364 KB Output is correct
3 Correct 23 ms 2712 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4052 KB Output is correct
2 Correct 11 ms 2132 KB Output is correct
3 Correct 4 ms 2772 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1236 KB Output is correct
2 Correct 4 ms 2772 KB Output is correct
3 Execution timed out 702 ms 8360 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3968 KB Output is correct
2 Correct 237 ms 7840 KB Output is correct
3 Correct 32 ms 3216 KB Output is correct
4 Correct 9 ms 2516 KB Output is correct