oj.uz

Submission #384154

# Submission time Handle Problem Language Result Execution time Memory
384154 2021-03-31T14:54:26 Z pure_mem Training (IOI07_training) C++14
100 / 100
 69 ms 8556 KB 
#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

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8044 KB Output is correct
2 Correct 14 ms 8044 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5224 KB Output is correct
2 Correct 5 ms 5100 KB Output is correct
3 Correct 37 ms 5612 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6508 KB Output is correct
2 Correct 40 ms 5484 KB Output is correct
3 Correct 10 ms 5996 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4844 KB Output is correct
2 Correct 6 ms 5868 KB Output is correct
3 Correct 69 ms 8556 KB Output is correct
4 Correct 8 ms 5868 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6508 KB Output is correct
2 Correct 50 ms 8172 KB Output is correct
3 Correct 14 ms 5996 KB Output is correct
4 Correct 31 ms 5740 KB Output is correct