oj.uz

Submission #135046

# Submission time Handle Problem Language Result Execution time Memory
135046 2019-07-23T14:59:30 Z arthur_nascimento Beads and wires (APIO14_beads) C++14
28 / 100
 4 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define maxn 1010

#define pii pair<int,int>

vector<pii> L[maxn];

int dp[2][2][maxn];

int get(int hat,int need,int vx,int p=-1){
  //  fprintf(stderr,"%d %d %d\n",need,vx,p);
     int &r = dp[hat][need][vx];
    if(r+1) return r;
    
    r = 0;
    int l = L[vx].size();
    if(need == 0){
        
        if(hat) {
            
            int stot= 0;
            vector<int> ss;
            for(int k=0;k<l;k++){
                    int to = L[vx][k].first;  //  fprintf(stderr,"to %d\n",to);
                    if(to != p)stot += max(get(0,0,to,vx), get(0,1,to,vx) + L[vx][k].second),
                                 ss.pb(max(get(0,0,to,vx), get(0,1,to,vx) + L[vx][k].second));
                    else ss.pb(0);
            }
            
            for(int i=0;i<l;i++)for(int j=i+1;j<l;j++){
                int A = L[vx][i].first, B = L[vx][j].first;
                if(A == p || B == p) continue;
                
                int s = max (L[vx][i].second + L[vx][j].second + get(0,0,A,vx) + get(1,0,B,vx),
                             L[vx][i].second + L[vx][j].second + get(1,0,A,vx) + get(0,0,B,vx));
                             
               /* for(int k=0;k<l;k++){
                    int to = L[vx][k].first;  //  fprintf(stderr,"to %d\n",to);
                    if(to != A && to != B && to != p) s += max(get(0,0,to,vx), get(0,1,to,vx) + L[vx][k].second);
                }*/
                s += stot - ss[i] - ss[j];
                r = max(r,s);
            }
        }
        int no = 0;
        for(int spec=0;spec<l;spec++){
            no=0;
            for(int k=0;k<l;k++){
                    int to = L[vx][k].first;
                    int hh = (hat && (spec==k));
                    if(to != p) no += max(get(hh,0,to,vx), get(hh,1,to,vx) + L[vx][k].second);
            }
            r = max(r,no);
        }
        r = max(r,no);
       // fprintf(stderr,"dp[%d][%d]=%d\n",need,vx,r);
        return r;
    }
    
    if(L[vx].size()==1){ 
        r = -1e7;
        return r;
    }
    for(int i=0;i<L[vx].size();i++){
        int s = 0;
        if(L[vx][i].first == p) continue;
        s = L[vx][i].second + get(hat,0,L[vx][i].first,vx);
        for(int j=0;j<L[vx].size();j++){
            int to = L[vx][j].first;
            if(to == p || i == j) continue;
            
            s += max(get(0,0,to,vx), get(0,1,to,vx) + L[vx][j].second);
        }
        r = max(r,s);
    }
    return r;
    
}

int main() {
    int n;
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c), a--, b--;
        L[a].pb(pii(b,c));
        L[b].pb(pii(a,c));
    }
    memset(dp,-1,sizeof(dp));
    printf("%d\n",get(1,0,0));
    //printf("%d\n",get(0,0,1));
}

Compilation message

beads.cpp: In function 'int get(int, int, int, int)':
beads.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<L[vx].size();i++){
                 ~^~~~~~~~~~~~~
beads.cpp:70:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<L[vx].size();j++){
                     ~^~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
beads.cpp:87:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&a,&b,&c), a--, b--;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 296 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 4 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 3 ms 376 KB Output is correct
22 Correct 3 ms 380 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 296 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 4 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 3 ms 376 KB Output is correct
22 Correct 3 ms 380 KB Output is correct
23 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 296 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 4 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 3 ms 376 KB Output is correct
22 Correct 3 ms 380 KB Output is correct
23 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -