oj.uz

Submission #521462

# Submission time Handle Problem Language Result Execution time Memory
521462 2022-02-02T07:41:06 Z Cantfindme Training (IOI07_training) C++17
82 / 100
 300 ms 12608 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end() 
 
const int maxn = 1010;
const int mod = 998244353; 
const int INF = LLONG_MAX/2;
 
typedef pair<pi, int> pii;
 
vector <int> adjlist[maxn];
 
int n, m;
int depth[maxn], pre[maxn], post[maxn];
map <int, int> mp[maxn];
int table[maxn][maxn];
 
vector <pii> edges[maxn];
vector <pii> eee;
 
int dp[maxn][1 << 10];
int parent[maxn];
int co = 0;
 
void dfs(int x, int p, int d) {
	pre[x] = co++;
	depth[x] = d;
	parent[x] = p;
	int cc = 0;
	for (auto i: adjlist[x]) if (i != p) {
		dfs(i,x, d + 1);
		mp[x][i] = (1 << cc);
		cc++;
	}
	post[x] = co - 1;
}
 
void setroot(int A, int B, int c) {
	int a = A, b = B;
	while (a != b) {
		if (depth[a] < depth[b]) swap(a,b); //a is the deeper one
		a = parent[a];
	}
	edges[a].push_back(pii(pi(A,B),c));
}
 
int dpf(int x, int bm);
 
int build(int x, int a, int b) {
	int res = 0;
	
	if (a != x) {
		res += dpf(a, 0);
		int l = a; 
		while (parent[l] != x) {
			res += dpf(parent[l], mp[parent[l]][l]);
			l = parent[l];
		}
	}
	
	if (b != x) {
		res += dpf(b,0);
		int r = b;
		while (parent[r] != x) {
			res += dpf(parent[r], mp[parent[r]][r]);
			r = parent[r];
		}
	}
	
	return res;
}
 
int findchild(int x, int a) {
	if (table[x][a] != 0) return table[x][a];
	
	if (pre[x] == pre[a]) return table[x][a] = x;
	for (auto i: adjlist[x]) if (i != parent[x]) {
		if (pre[i] <= pre[a] and post[i] >= pre[a]) {
			return table[x][a] = i;
		}
	}
	assert(0);
	return -1;
}
 
int dpf(int x, int bm) {
	if (dp[x][bm] != -1) return dp[x][bm];
	int res = 0;
	
	//Dont build any edges with x as root
	for (auto i: adjlist[x]) if (i != parent[x]) {
		if (mp[x][i] & bm) continue;
		res += dpf(i,0);
	}
	
	//Build some edge with x as root
	for (auto [cur,c] : edges[x]) {
		auto [a,b] = cur;
		int l = findchild(x, a), r = findchild(x,b);
		if (bm & mp[x][l] or bm & mp[x][r]) continue;
		
		res = max(res, build(x,a,b) + c + dpf(x, bm | mp[x][l] | mp[x][r]));
	}
	
	return dp[x][bm] = res;
}
 
int32_t main() {
	FAST
	int rans = 0;
	cin >> n >> m;
	for (int i =0;i<m;i++) {
		int a, b, c; cin >> a >> b >> c;
		if (c == 0) {
			adjlist[a].push_back(b);
			adjlist[b].push_back(a);
		} else {
			rans += c;
			eee.push_back(pii(pi(a,b),c));
		}
	}
	
	dfs(1, -1, 0);
	for (auto [cur, c] : eee) {
		auto [a,b] = cur;
		if ((depth[a] + depth[b]) % 2 == 1) continue;
		setroot(a,b,c);
	}
	
	//for (int i =1;i<=n;i++) {
		//cout << i << "\n";
		//for (auto [cur,c] : edges[i]) {
			//auto [a,b]  = cur;
			//cout << a << " " << b << " " << c << "\n";
		//}
	//}
	
	memset(dp,-1,sizeof dp);
	cout << rans - dpf(1,0);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8664 KB Output is correct
2 Correct 4 ms 8704 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11524 KB Output is correct
2 Correct 12 ms 12608 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8652 KB Output is correct
2 Correct 4 ms 8652 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8780 KB Output is correct
2 Correct 5 ms 8780 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9372 KB Output is correct
2 Correct 6 ms 9036 KB Output is correct
3 Correct 81 ms 8792 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10444 KB Output is correct
2 Correct 44 ms 9020 KB Output is correct
3 Correct 11 ms 9820 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8752 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Execution timed out 634 ms 8988 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9420 KB Output is correct
2 Execution timed out 344 ms 11604 KB Time limit exceeded
3 Halted 0 ms 0 KB -