Submission #521461

#	Time	Username	Problem	Language	Result	Execution time	Memory
521461		Cantfindme	Training (IOI07_training)	C++17	100 / 100	45 ms	24724 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 dp2[maxn][maxn];
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 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 solve(int x, int below) {
	if (dp2[x][below] != -1) return dp2[x][below];
	int res = 0;
		
	if (x == below) {
		res = dpf(x, 0);
	} else {
		int c = findchild(x, below);
		int bm = mp[x][c];
		res = dpf(x, bm) + solve(c, below);
	}
	
	return dp2[x][below] = res;
}

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;
		
		int res2 = c + dpf(x, bm | mp[x][l] | mp[x][r]);
		if (l != x) res2 += solve(l,a);
		if (r != x) res2 += solve(r,b);
		
		res = max(res, res2);
	}
	
	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);
	memset(dp2,-1,sizeof dp2);
	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: 9 / 9
• Subtask 11: 9 / 9