oj.uz

Submission #19169

# Submission time Handle Problem Language Result Execution time Memory
19169 2016-02-19T08:41:21 Z comet Beads and wires (APIO14_beads) C++
0 / 100
 5 ms 3456 KB 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cassert>
#include <queue>
#define pb push_back
using namespace std;
typedef pair<int,int> pp;
struct pt{int u,c;};
typedef vector<int> vec;
typedef vector<pt> vec2;
typedef vector<vec2> graph;
graph path;

int N;
int root;
int dp[200010][4];

void input(){
	scanf("%d",&N);
	path.assign(N+1,vec2());
	int x,y,z;
	for(int i=0;i<N-1;i++){
		scanf("%d%d%d",&x,&y,&z);
		path[x].pb(pt{y,z});
		path[y].pb(pt{x,z});
	}
}

int getMax2(vec& s){
	int Max1=-1e9,Max2=-1e9;
	for(int i=0;i<s.size();i++){
		if(s[i]>=Max1){
			Max2=Max1;
			Max1=s[i];
		}else if(s[i]>Max2){
			Max2=s[i];
		}
	}
	return max(0,Max1+Max2);
}

int getMax1(vec& s){
	return *max_element(s.begin(),s.end());
}

void process(int v,int p,int mode){
	int sz=path[v].size();
	int cnt=sz-(v!=root);
	int& ret=dp[v][mode];
	ret=0;
	if(cnt==0){
		if(mode==1||mode==3)ret=-1e9;
		return;
	}

	vec a;
	for(int i=0;i<sz;i++){
		int u=path[v][i].u;
		int c=path[v][i].c;
	
		if(p==u)continue;
		int z;
		if(mode==1||mode==3){
			z = max(dp[u][2],dp[u][3]+c);
		}else if(mode==0||mode==2){
			z = max(dp[u][0+mode],dp[u][1+mode]+c);
		}
		ret+=z;
		if(mode==0||mode==3){
			a.pb(dp[u][2]+c-z);
		}
		if(mode==1){
			a.pb(dp[u][0]+c-z);
		}
	}
	
	if(mode==0){
		if(cnt>=2){
			ret+=getMax2(a);
		}
	}else if(mode==1||mode==3){
		ret+=getMax1(a);
	}
}

void dfs(int v,int p,int mode){

	int& ret=dp[v][mode];
	if(~ret)return;

	for(int i=0;i<path[v].size();i++){
		int u=path[v][i].u;
		if(u==p)continue;
		for(int j=0;j<4;j++){
			dfs(u,v,j);
		}
	}
	process(v,p,mode);
}

void PS(){
	
	memset(dp,-1,sizeof(dp));

	for(int i=1;i<=N;i++){
		if(path[i].size()==1){
			root=i;
			break;
		}
	}

	dfs(root,root,0);
	printf("%d\n",dp[root][0]);
}

int main(){
	input();
	PS();
	return 0;
}

Compilation message

beads.cpp: In function 'int getMax2(vec&)':
beads.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.size();i++){
              ~^~~~~~~~~
beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:93:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<path[v].size();i++){
              ~^~~~~~~~~~~~~~~
beads.cpp: In function 'void input()':
beads.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
beads.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&x,&y,&z);
   ~~~~~^~~~~~~~~~~~~~~~~~~
beads.cpp: In function 'void process(int, int, int)':
beads.cpp:75:19: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
    a.pb(dp[u][0]+c-z);
         ~~~~~~~~~~^~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3364 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct
3 Correct 4 ms 3456 KB Output is correct
4 Correct 4 ms 3456 KB Output is correct
5 Correct 5 ms 3456 KB Output is correct
6 Correct 5 ms 3456 KB Output is correct
7 Incorrect 4 ms 3428 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3364 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct
3 Correct 4 ms 3456 KB Output is correct
4 Correct 4 ms 3456 KB Output is correct
5 Correct 5 ms 3456 KB Output is correct
6 Correct 5 ms 3456 KB Output is correct
7 Incorrect 4 ms 3428 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3364 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct
3 Correct 4 ms 3456 KB Output is correct
4 Correct 4 ms 3456 KB Output is correct
5 Correct 5 ms 3456 KB Output is correct
6 Correct 5 ms 3456 KB Output is correct
7 Incorrect 4 ms 3428 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3364 KB Output is correct
2 Correct 4 ms 3456 KB Output is correct
3 Correct 4 ms 3456 KB Output is correct
4 Correct 4 ms 3456 KB Output is correct
5 Correct 5 ms 3456 KB Output is correct
6 Correct 5 ms 3456 KB Output is correct
7 Incorrect 4 ms 3428 KB Output isn't correct
8 Halted 0 ms 0 KB -