oj.uz

Submission #54606

# Submission time Handle Problem Language Result Execution time Memory
54606 2018-07-04T07:56:51 Z 김세빈(#1491) Training (IOI07_training) C++11
100 / 100
 22 ms 9012 KB 
#include <bits/stdc++.h>

using namespace std;

vector <int> V[1010], T[1010];
int P[1010], D[1010];
int M[1010][1010];
int A[5050], B[5050], C[5050];
int X[1010][1100];
int n, m, k, sum, ans;

void dfs(int p, int r)
{
	for(auto t: T[p]){
		if(t != r){
			P[t] = p;
			D[t] = D[p] + 1;
			dfs(t, p);
		}
	}
}

int lca(int a, int b)
{
	if(D[a] < D[b]) swap(a, b);
	
	for(;D[a] != D[b];) a = P[a];
	for(;a != b;) a = P[a], b = P[b];
	
	return a;
}

void dp(int p, int r)
{
	int a, b, x, y, s, i;
	int cnt = 0;
	
	for(auto t: T[p]){
		if(t != r){
			dp(t, p);
			cnt += X[t][1023];
		}
	}
	
	for(i=0;i<1024;i++) X[p][i] = cnt;
	
	for(auto t: V[p]){
		a = A[t], b = B[t], s = C[t];
		x = y = 0;
		
		for(;a!=p;){
			if(x) s += X[a][1023 - (1 << M[a][x])] - X[x][1023];
			else s += X[a][1023];
			x = a, a = P[a];
		}
		
		for(;b!=p;){
			if(y) s += X[b][1023 - (1 << M[b][y])] - X[y][1023];
			else s += X[b][1023];
			y = b, b = P[b];
		}
		
		b = 0;
		if(x) s -= X[x][1023], b |= 1 << M[p][x];
		if(y) s -= X[y][1023], b |= 1 << M[p][y];
		
//		printf("* %d %d\n", b, s);
		
		for(i=0;i<1024;i++) if(!(i & b)){
			X[p][i+b] = max(X[p][i+b], X[p][i] + s);
		}
	}
	
//	printf("%d %d\n", p, X[p][1023]);
}

int main()
{
	int i, j, a, b, c;
	
	scanf("%d%d", &n, &m);
	
	for(i=0;i<m;i++){
		scanf("%d%d%d", &a, &b, &c);
		if(c == 0) T[a].push_back(b), T[b].push_back(a);
		else A[k] = a, B[k] = b, C[k++] = c;
		sum += c;
	}
	
	for(i=1;i<=n;i++){
		for(j=0;j<T[i].size();j++){
			M[i][T[i][j]] = j;
		}
	}
	
	dfs(1, 0);
	
	for(i=0;i<k;i++){
		if(~(D[A[i]] + D[B[i]]) & 1){
			V[lca(A[i], B[i])].push_back(i);
		}
	}
	
	dp(1, 0);
	
	for(i=0;i<1024;i++){
		ans = max(ans, X[1][i]);
	}
	
	printf("%d\n", sum - ans);
	
	return 0;
}

Compilation message

training.cpp: In function 'int main()':
training.cpp:91:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<T[i].size();j++){
           ~^~~~~~~~~~~~
training.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
training.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 660 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8984 KB Output is correct
2 Correct 15 ms 8984 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8984 KB Output is correct
2 Correct 5 ms 8984 KB Output is correct

Subtask #8
9.0 / 9.0

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

Subtask #9
9.0 / 9.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8984 KB Output is correct
2 Correct 9 ms 8984 KB Output is correct
3 Correct 22 ms 9012 KB Output is correct
4 Correct 9 ms 9012 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 9012 KB Output is correct
2 Correct 22 ms 9012 KB Output is correct
3 Correct 17 ms 9012 KB Output is correct
4 Correct 14 ms 9012 KB Output is correct