oj.uz

Submission #54585

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

using namespace std;

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

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 rt = 0;
	
	for(auto t: T[p]){
		if(t != r){
			dp(t, p);
			rt += K[t];
		}
	}
	
	for(auto t: T[p]){
		if(t != r) R[p][t] = rt - K[t];
	}
	
	for(i=0;i<1024;i++) X[i] = 0;
	
	for(auto t: V[p]){
		a = A[t], b = B[t], s = C[t];
		x = y = 0;
		
		for(;a!=p;){
			s += R[a][x];
			x = a, a = P[a];
		}
		
		for(;b!=p;){
			s += R[b][y];
			y = b, b = P[b];
		}
		
		for(auto q: T[p]) if(q != x && q != y) s += K[q];
			
		b = 0;
		if(x) b |= 1 << M[p][x];
		if(y) b |= 1 << M[p][y];
		
		rt = max(rt, s);
	/*	
		for(i=0;i<1024;i++) if(!(i & b)){
			X[i+b] = max(X[i+b], X[i] + s);
			rt = max(rt, X[i+b]);
		}*/
	}
	
	R[p][0] = K[p] = rt;
	
//	printf("%d %d\n", p, K[p]);
}

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);
	
	printf("%d\n", sum - K[1]);
	
	return 0;
}

Compilation message

training.cpp: In function 'int main()':
training.cpp:98:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<T[i].size();j++){
           ~^~~~~~~~~~~~
training.cpp:88: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:91: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 612 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8468 KB Output is correct
2 Correct 11 ms 8468 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 8468 KB Output isn't correct
2 Halted 0 ms 0 KB -