Submission #13476

#	Time	Username	Problem	Language	Result	Execution time	Memory
13476		ainta	Beads and wires (APIO14_beads)	C++98	13 / 100	11 ms	9756 KiB

beads

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>E[200100], L[200100];
int pL[201000], n, D[201000][4];
void DFS(int a, int pp){
	int i, x, t1, t2, t3, t4, S = 0, S2 = 0, M1, M2, t, tt, M3, M4, x1, x2, x3, x4;
	for (i = 0; i < E[a].size(); i++){
		if (E[a][i] != pp){
			pL[E[a][i]] = L[a][i];
			DFS(E[a][i], a);
		}
	}
	D[a][1] = D[a][2] = D[a][3] = -999999999;
	if (!E[a].size())return;
	M1 = M2 = M3 = M4 = -999999999;
	x1 = x2 = x3 = x4 = -1;
	for (i = 0; i < E[a].size(); i++){
		x = E[a][i];
		if (x == pp)continue;
		t1 = D[x][0];
		t2 = D[x][1] + pL[x];
		t3 = D[x][2] + pL[x];
		t4 = D[x][3];
		tt = max(max(t1, t2), t4);
		t = max(t3, tt);
		S += t;
		S2 += tt;
		t1 = D[x][0] + pL[x] - tt;
		t2 = D[x][3] + pL[x] - tt;
		if (M1 < t1){ M2 = M1, x2 = x1; M1 = t1, x1 = i; }
		else if (M2 < t1) M2 = t1, x2 = i;
		if (M3 < t2){ M4 = M3, x4 = x3; M3 = t2, x3 = i; }
		else if (M4 < t2) M4 = t2, x4 = i;
	}
	D[a][0] = S;
	D[a][1] = S2 + M1;
	D[a][2] = S2 + M3;
	if (E[a].size() >= 2){
		t1 = M1 + M2;
		if (x1 == x3) t2 = max(M1 + M4, M2 + M3);
		else t2 = M1 + M3;
		D[a][3] = S2 + max(t1, t2);
	}
}
int main(){
	int i, a, b, d;
	scanf("%d", &n);
	for (i = 1; i < n; i++){
		scanf("%d%d%d", &a, &b, &d);
		E[a].push_back(b); E[b].push_back(a);
		L[a].push_back(d); L[b].push_back(d);
	}
	DFS(1, 0);
	printf("%d\n", max(D[1][0], D[1][3]));
}

Compilation message (stderr)

beads.cpp: In function 'void DFS(int, int)':
beads.cpp:9:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[a].size(); i++){
              ~~^~~~~~~~~~~~~
beads.cpp:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[a].size(); i++){
              ~~^~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43