oj.uz

Submission #521461

# Submission time Handle Problem Language Result Execution time Memory
521461 2022-02-02T07:40:08 Z Cantfindme Training (IOI07_training) C++17
100 / 100
 45 ms 24724 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 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16520 KB Output is correct
2 Correct 7 ms 16460 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16716 KB Output is correct
2 Correct 8 ms 16708 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24640 KB Output is correct
2 Correct 25 ms 24724 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16460 KB Output is correct
2 Correct 10 ms 16516 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17100 KB Output is correct
2 Correct 8 ms 16972 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17460 KB Output is correct
2 Correct 11 ms 17352 KB Output is correct
3 Correct 29 ms 18568 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20044 KB Output is correct
2 Correct 30 ms 18112 KB Output is correct
3 Correct 13 ms 18892 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 17028 KB Output is correct
2 Correct 10 ms 18636 KB Output is correct
3 Correct 45 ms 21892 KB Output is correct
4 Correct 12 ms 18924 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 20428 KB Output is correct
2 Correct 39 ms 24580 KB Output is correct
3 Correct 15 ms 19516 KB Output is correct
4 Correct 30 ms 18724 KB Output is correct