Submission #33984

#	Time	Username	Problem	Language	Result	Execution time	Memory
33984		mohammad_kilani	Beads and wires (APIO14_beads)	C++14	0 / 100	2 ms	384 KiB

beads

    #include <bits/stdc++.h>
    using namespace std;
    #define mod 1000000007
    #define oo 2000000000
    const int N = 210;
    int n;
    long long dp[N][2];
    vector< pair<int,int> > g[N];
     
    long long solve(int node,int prnt,int len,bool b){
    	if(dp[node][b] != -1) return dp[node][b];
    	long long sum = 0 ;
    	dp[node][b] = 0 ;
    	for(int i=0;i<g[node].size();i++){
    		int newnode = g[node][i].first;
    		int newlen = g[node][i].second;
    		if(newnode != prnt){
    			long long cur = solve(newnode,node,newlen,0);
    			sum+= cur;
    		}
    	}
    	dp[node][b] = sum;
    	if(b == 0){
    		for(int i=0;i<g[node].size();i++){
    			int newnode = g[node][i].first;
    			int newlen = g[node][i].second;
    			if(newnode == prnt) continue;
    			long long cur = solve(newnode,node,newlen,0);
    			long long cur2 = solve(newnode,node,newlen,1);
    			dp[node][b] = max(dp[node][b],sum - cur + cur2 + newlen + len);
    		}
    		for(int i=0;i<g[node].size();i++){
    			for(int j=i+1;j<g[node].size();j++){
    				int node1 = g[node][i].first;
    				int node2 = g[node][j].first;
    				int len1 = g[node][i].second;
    				int len2 = g[node][j].second;
    				if(node1 == prnt || node2 == prnt) continue;
    				long long cur1 = solve(node1,node,len1,0);
    				long long cur2 = solve(node1,node,len1,1);
    				long long cur3 = solve(node2,node,len2,0);
    				long long cur4 = solve(node2,node,len2,1);
    				dp[node][b] = max(dp[node][b],sum + cur4 - cur3 + len1 + cur2 - cur1 + len2); 
    			}
    		}
    	}
    	return dp[node][b];
    }
     
    int main() {
    	//freopen("in.txt","r",stdin);
    	scanf("%d",&n);
    	for(int i=0;i<n-1;i++){
    		int u , v, w;
    		scanf("%d%d%d",&u,&v,&w);
    		g[u].push_back(make_pair(v,w));
    		g[v].push_back(make_pair(u,w));
    	}
    	long long ans = 0 ;
    	for(int i=1;i<=n;i++){
    		if(g[i].size() == 1){
    			memset(dp,-1,sizeof(dp));
    			ans = max(ans,solve(i,-1,0,1));
    			break;
    		}
    	}
    	cout << ans << endl;
    	return 0;
    }

Compilation message (stderr)

beads.cpp: In function 'long long int solve(int, int, int, bool)':
beads.cpp:14:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i=0;i<g[node].size();i++){
                  ~^~~~~~~~~~~~~~~
beads.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<g[node].size();i++){
                   ~^~~~~~~~~~~~~~~
beads.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<g[node].size();i++){
                   ~^~~~~~~~~~~~~~~
beads.cpp:33:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int j=i+1;j<g[node].size();j++){
                      ~^~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:52:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d",&n);
      ~~~~~^~~~~~~~~
beads.cpp:55:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d%d",&u,&v,&w);
       ~~~~~^~~~~~~~~~~~~~~~~~~

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