oj.uz

Submission #54564

# Submission time Handle Problem Language Result Execution time Memory
54564 2018-07-04T06:11:42 Z 김세빈(#1491) Training (IOI07_training) C++11
20 / 100
 300 ms 864 KB 
#include <bits/stdc++.h>

using namespace std;

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

int main()
{
	int i, 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;
	}
	
	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:78: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:81: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 380 KB Output is correct
2 Correct 2 ms 540 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 660 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 660 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 660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 864 KB Time limit exceeded
2 Halted 0 ms 0 KB -