Submission #13477

#	Time	Username	Problem	Language	Result	Execution time	Memory
13477		ainta	Beads and wires (APIO14_beads)	C++98	100 / 100	350 ms	31888 KiB

beads

#include<stdio.h>
#include<algorithm>
#include<vector>
#define INF 999999999
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, x3, MM, MM2;
	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] = -INF;
	MM2 = MM = M1 = M2 = M3 = M4 = -INF;
	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];
		t = max(t1, t2);
		S += t;
		t3 = D[x][2], t4 = D[x][3] + pL[x];
		tt = max(t3, t4);
		MM = max(MM, tt - t);
		t1 = D[x][0] + pL[x] - t;
		t2 = D[x][2] + pL[x] - t;
		MM2 = max(MM2, t2);
		if (M1 < t1){ M2 = M1; M1 = t1, x1 = i; }
		else if (M2 < t1)M2 = t1;
		if (M3 < t2){ M4 = M3; M3 = t2, x3 = i; }
		else if (M4 < t2)M4 = t2;
	}
	D[a][0] = S;
	if (!E[a].size())return;
	D[a][1] = S + M1;
	D[a][2] = S + MM;
	if (E[a].size() >= 2){
		t1 = M1 + M2;
		if (x1 == x3)t2 = max(M1 + M4, M2 + M3);
		else t2 = M1 + M3;
		D[a][2] = max(D[a][2], S + max(t1, t2));
	}
	D[a][3] = S + MM2;
}
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][2]));
}

Compilation message (stderr)

beads.cpp: In function 'void DFS(int, int)':
beads.cpp:10:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[a].size(); i++){
              ~~^~~~~~~~~~~~~
beads.cpp:18:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[a].size(); i++){
              ~~^~~~~~~~~~~~~
beads.cpp:9:35: warning: unused variable 'S2' [-Wunused-variable]
  int i, x, t1, t2, t3, t4, S = 0, S2 = 0, M1, M2, t, tt, M3, M4, x1, x3, MM, MM2;
                                   ^~
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: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43