Submission #384154

#	Time	Username	Problem	Language	Result	Execution time	Memory
384154		pure_mem	Training (IOI07_training)	C++14	100 / 100	69 ms	8556 KiB

training

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e3 + 1, M = 5e3 + 1, INF = 1e9;
const ll mod = 1e9 + 7;

int n, m, cost[M], tin[N], tout[N], cash[M], timer;
int h[N], parent[N], dp[(1 << 10)][N], rc[N][N];
pair<int, int> road[M];
vector< int > g[N], ch[N], maybe[N];

void dfs(int v, int pr){
	parent[v] = pr, tin[v] = ++timer;
	int j = 0;
	for(int to: g[v]){
		if(to != pr){
			h[to] = h[v] + 1, ch[v].push_back(to), rc[v][to] = j++;
			dfs(to, v);
		}
	}
	tout[v] = ++timer;
}
bool check(int x, int y){
	return (tin[x] <= tin[y] && tout[y] <= tout[x]);
}
int solve(int v, int mask){
	if(dp[v][mask] != -1)
		return dp[v][mask];
	int &res = dp[v][mask];
	res = 0;
	for(int i = 0;i < ch[v].size();i++){
		if((mask >> i) & 1)
			continue;
		res += solve(ch[v][i], 0);
	}
	for(int id: maybe[v]){
		int x = road[id].X, y = road[id].Y, newmask = mask, opt = 0;
		for(int i = 0;i < ch[v].size();i++){
  			if(check(ch[v][i], y))
  				swap(x, y);
  			if(check(ch[v][i], x)){
  				newmask ^= (1 << i);
  				if(cash[id] == -1){
  					int tmp = parent[x], last = x;
  					while(tmp != v){
  						opt += solve(tmp, 1 << (rc[tmp][last]));
  						last = tmp, tmp = parent[tmp];
  					}
  					opt += solve(x, 0);
  				}
  			}
		}
		if(cash[id] == -1)
			cash[id] = opt;
		if((newmask & mask) != mask)
			continue;
		opt = solve(v, newmask) + cost[id] + cash[id];
		res = max(res, opt);
	}
	return res;	
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	memset(dp, -1, sizeof(dp)), memset(cash, -1, sizeof(cash));
	cin >> n >> m;
	for(int i = 1, x, y;i <= m;i++){
		cin >> x >> y >> cost[i], road[i] = MP(x, y);
		if(!cost[i])
			g[x].push_back(y), g[y].push_back(x);
	}
	dfs(1, 1);
	int all = 0;
	for(int i = 1;i <= m;i++){
		if(!cost[i])
			continue;
		all += cost[i];
		int x = road[i].X, y = road[i].Y;
		if((h[x] + h[y]) & 1)
			continue;
	//	cerr << x << " " << y << "\n";
		while(x != y){
			if(h[x] < h[y])
				swap(x, y);
			x = parent[x];	
		}
		maybe[x].push_back(i);
	}
	solve(1, 0);
	cout << all - dp[1][0];
}

Compilation message (stderr)

training.cpp: In function 'int solve(int, int)':
training.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i = 0;i < ch[v].size();i++){
      |                ~~^~~~~~~~~~~~~~
training.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int i = 0;i < ch[v].size();i++){
      |                 ~~^~~~~~~~~~~~~~

• 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