Submission #33634

#	Time	Username	Problem	Language	Result	Execution time	Memory
33634		comtalyst	Beads and wires (APIO14_beads)	C++14	100 / 100	240 ms	23612 KiB

beads

/*
 *	Task: apio14_beads
 *	Lang: C/C++11
 *	Author: comtalyst
 *	Site: oj.uz
 *	Last Update: 31/10/2017
 */

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
using namespace std;

/* Note
----------------------------
Learned : 
Bugs found & solved :
- bad state definition (many subbugs)
Optimizations :
----------------------------
0 = Void 	[0],[1]
1 = Core 	[0]
2 = Halfcore with void 	[0],[1]
3 = Halfcore with core 	[0]
Every Core must match with Void+Void or Core+Void
3rd state : can this joints to dad node? (joint = connect by it, not its dad)
*/	

#define x first
#define y second
#define umap unordered_map
#define pqueue priority_queue
#define mset multiset
#define mp make_pair
#define mt make_tuple
#define long long long
#define MOD 1000000007
#define MAX (int)1e9
#define MIN (int)-1e9
#define FILEIN_ freopen("__in.txt","r",stdin)
#define FILEOUT_ freopen("__out.txt","w",stdout)
#define FILEIN(text) freopen(text,"r",stdin)
#define FILEOUT(text) freopen(text,"w",stdout)

int data[200005][4][2];
vector<pair<int,int>> adl[200005];
int dp(int x,int f){
	int i,y,w,sxc=0,sxc2=0,v;
	pair<int,int> mxv01={MIN,MIN},mxv02={MIN,MIN},mxc1={MIN,MIN},mxc2={MIN,MIN},mxd={MIN,MIN},mxv11={MIN,MIN},mxv12={MIN,MIN};
	for(i = 0; i < adl[x].size(); i++){
		y = adl[x][i].x;
		w = adl[x][i].y;
		if(y == f) continue;
		dp(y,x);
	}
	for(i = 0; i < adl[x].size(); i++){
		y = adl[x][i].x;
		w = adl[x][i].y;
		if(y == f) continue;
		v = max(data[y][0][1],data[y][2][1]+w);
		data[x][0][1] += v;
		if(max(data[y][0][0],max(data[y][1][0],max(data[y][2][0]+w,data[y][3][0]+w))) -v > mxd.x){
			mxd = {max(data[y][0][0],max(data[y][1][0],max(data[y][2][0]+w,data[y][3][0]+w))) -v,y};
		}
	}
	data[x][0][0] = data[x][0][1]+mxd.x;
	for(i = 0; i < adl[x].size(); i++){
		y = adl[x][i].x;
		w = adl[x][i].y;
		if(y == f) continue;
		v = max(data[y][0][1],data[y][2][1]+w);
		data[x][1][0] += v;
		data[x][2][0] += v;
		data[x][2][1] += v;
		data[x][3][0] += v;
		if(data[y][0][0]+w -v > mxv01.x){
			mxv02 = mxv01;
			mxv01 = {data[y][0][0]+w -v,y};
		}
		else if(data[y][0][0]+w -v > mxv02.x){
			mxv02 = {data[y][0][0]+w -v,y};
		}
		if(data[y][0][1]+w -v > mxv11.x){
			mxv12 = mxv11;
			mxv11 = {data[y][0][1]+w -v,y};
		}
		else if(data[y][0][1]+w -v > mxv12.x){
			mxv12 = {data[y][0][1]+w -v,y};
		}
		if(data[y][1][0]+w -v > mxc1.x){
			mxc2 = mxc1;
			mxc1 = {data[y][1][0]+w -v,y};
		}
		else if(data[y][1][0]+w -v > mxc2.x){
			mxc2 = {data[y][1][0]+w -v,y};
		}
	}
	if(mxv11.y == mxc1.y){
		if(mxv11.y == mxv01.y){
			data[x][1][0] = data[x][1][0]+max(max(mxv11.x+mxv12.x,max(mxv11.x+mxv02.x,mxv12.x+mxv01.x)),max(mxv11.x+mxc2.x,mxv12.x+mxc1.x));
		}
		else{
			data[x][1][0] = data[x][1][0]+max(max(mxv11.x+mxv12.x,mxv11.x+mxv01.x),max(mxv11.x+mxc2.x,mxv12.x+mxc1.x));
		}
	}
	else{
		if(mxv11.y == mxv01.y){
			data[x][1][0] = data[x][1][0]+max(max(mxv11.x+mxv12.x,max(mxv11.x+mxv02.x,mxv12.x+mxv01.x)),mxv11.x+mxc1.x);
		}
		else{
			data[x][1][0] = data[x][1][0]+max(max(mxv11.x+mxv12.x,mxv11.x+mxv01.x),mxv11.x+mxc1.x);
		}
	}
	data[x][2][0] += mxv01.x;
	data[x][2][1] += mxv11.x;
	data[x][3][0] += mxc1.x;

	//printf("%d :\n%d %d %d %d\n%d %d %d %d\n",x,mxe1,mxe2,mxd1,mxd2,data[x][0],data[x][1],data[x][2],data[x][4]);
}

main(){
	int t,i,j,n,m,x,y,w;
	
	//FILEIN_;
	//FILEOUT_;

	scanf("%d",&n);
	for(i = 1; i < n; i++){
		scanf("%d %d %d",&x,&y,&w);
		adl[x].emplace_back(y,w);
		adl[y].emplace_back(x,w);
	}
	dp(1,0);
	printf("%d\n",max(max(data[1][0][0],data[1][0][1]),data[1][1][0]));

	return 0;	
}

Compilation message (stderr)

beads.cpp: In function 'int dp(int, int)':
beads.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < adl[x].size(); i++){
             ~~^~~~~~~~~~~~~~~
beads.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < adl[x].size(); i++){
             ~~^~~~~~~~~~~~~~~
beads.cpp:66:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < adl[x].size(); i++){
             ~~^~~~~~~~~~~~~~~
beads.cpp:47:12: warning: unused variable 'sxc' [-Wunused-variable]
  int i,y,w,sxc=0,sxc2=0,v;
            ^~~
beads.cpp:47:18: warning: unused variable 'sxc2' [-Wunused-variable]
  int i,y,w,sxc=0,sxc2=0,v;
                  ^~~~
beads.cpp:118:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
beads.cpp: At global scope:
beads.cpp:120:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
beads.cpp: In function 'int main()':
beads.cpp:121:6: warning: unused variable 't' [-Wunused-variable]
  int t,i,j,n,m,x,y,w;
      ^
beads.cpp:121:10: warning: unused variable 'j' [-Wunused-variable]
  int t,i,j,n,m,x,y,w;
          ^
beads.cpp:121:14: warning: unused variable 'm' [-Wunused-variable]
  int t,i,j,n,m,x,y,w;
              ^
beads.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
beads.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&x,&y,&w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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