Submission #74070

#	Time	Username	Problem	Language	Result	Execution time	Memory
74070		KLPP	Beads and wires (APIO14_beads)	C++14	0 / 100	4 ms	2688 KiB

beads

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef long long int lld;
#define INF 1000000000000000
vector<pair<int,lld> > tree[100000];
lld DP[10000][2];

lld trabalha(int node,bool used){
	if(DP[node][used]!=-1)return DP[node][used];
	if(tree[node].size()==0){
		if(used){
			DP[node][1]=-INF;
			return DP[node][1];
		}else{
			DP[node][0]=0;
			return 0;
		}
	}
	lld DP2[tree[node].size()+1][3][2];
	for(int i=0;i<=tree[node].size();i++){
		DP2[i][0][0]=-INF;
		DP2[i][0][1]=-INF;
		DP2[i][1][0]=-INF;
		DP2[i][1][1]=-INF;
		DP2[i][2][0]=-INF;
		DP2[i][2][1]=-INF;
	}
	DP2[0][0][0]=0;
	for(int i=0;i<tree[node].size();i++){
		int vertex=tree[node][i].first;
		lld weight=tree[node][i].second;
		//cout<<weight<<endl;
		for(int j=0;j<=2;j++){
			for(int k=0;k<2;k++){
				//cout<<DP2[i][j][k]<<" "<<vertex<<" "<<weight<<" "<<trabalha(vertex,0)<<endl;
				DP2[i+1][j][k]=max(DP2[i+1][j][k],DP2[i][j][k]+trabalha(vertex,0));
				DP2[i+1][j][k]=max(DP2[i+1][j][k],DP2[i][j][k]+trabalha(vertex,1)+weight);
				if(j<2){
					DP2[i+1][j+1][k]=max(DP2[i+1][j+1][k],DP2[i][j][k]+trabalha(vertex,0)+weight);
				}
				if(k<1){
					DP2[i+1][j][k+1]=max(DP2[i+1][j][k+1],DP2[i][j][k]+trabalha(vertex,0)+weight);
				}
			}
		}
		/*for(int i=0;i<=tree[node].size();i++){
			for(int j=0;j<=2;j++){
				for(int k=0;k<2;k++){
					cout<<DP2[i][j][k]<<" ";
				}
			}cout<<endl;
		}*/
	}
	/*for(int i=0;i<tree[node].size();i++)cout<<tree[node][i].second<<endl;
	for(int i=0;i<=tree[node].size();i++){
		for(int j=0;j<=2;j++){
			for(int k=0;k<2;k++){
				cout<<DP2[i][j][k]<<" ";
			}
		}cout<<endl;
	}*/
	DP[node][used]=max(DP2[tree[node].size()][0][used],DP2[tree[node].size()][2][used]);
	return DP[node][used];
}
int main(){
	int n;
	cin>>n;
	vector<pair<int,lld> >nei[n];
	for(int i=0;i<n-1;i++){
		int x,y;
		cin>>x>>y;
		x--;y--;
		lld z;
		cin>>z;
		nei[x].push_back(pair<int,lld>(y,z));
		nei[y].push_back(pair<int,lld>(x,z));
	}
	queue<int> q;
	int dist[n];
	for(int i=0;i<n;i++)dist[i]=-1;
	dist[0]=0;
	q.push(0);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<nei[u].size();i++){	
			int v=nei[u][i].first;
			if(dist[v]==-1){
				dist[v]=dist[u]+1;
				q.push(v);
			}
		}
	}
	for(int i=0;i<n;i++){DP[i][0]=-1;
		DP[i][1]=-1;
		for(int j=0;j<nei[i].size();j++){
			int u=nei[i][j].first;
			if(dist[u]>dist[i]){
				tree[i].push_back(nei[i][j]);
				//cout<<i<<" "<<u<<endl;
			}
		}
	}
	cout<<trabalha(0,0)<<endl;
	//for(int i=0;i<n;i++)cout<<DP[i][0]<<" "<<DP[i][1]<<endl;
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'lld trabalha(int, bool)':
beads.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<=tree[node].size();i++){
              ~^~~~~~~~~~~~~~~~~~~
beads.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tree[node].size();i++){
              ~^~~~~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:87:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<nei[u].size();i++){ 
               ~^~~~~~~~~~~~~~
beads.cpp:97:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<nei[i].size();j++){
               ~^~~~~~~~~~~~~~

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