Submission #521462

#	Time	Username	Problem	Language	Result	Execution time	Memory
521462		Cantfindme	Training (IOI07_training)	C++17	82 / 100	634 ms	12608 KiB

training

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9