oj.uz

Submission #13056

# Submission time Handle Problem Language Result Execution time Memory
13056 2015-01-27T16:14:00 Z gs14004 Beads and wires (APIO14_beads) C++14
0 / 100
 7 ms 6656 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int,int> pi;

vector<pi> graph[200005];
int n;
int dp[200005][2];

int f(int x, int m, int pa, int e){
    if(~dp[x][m]) return dp[x][m];
    if(m == 0){
        int r = 0;
        vector<int> addi;
        for (int i=0; i<graph[x].size(); i++) {
            pi t = graph[x][i];
            if(t.second == pa) continue;
            int classic = f(t.second,0,x,t.first);
            int pick = f(t.second,1,x,t.first);
            int free = t.first;
            r += max(classic,pick);
            addi.push_back(classic + free - max(classic,pick));
        }
        int r2 = 0;
        if(addi.size() >= 2){
            auto x = max_element(addi.begin(),addi.end());
            r2 += *x;
            *x = -1e9;
            x = max_element(addi.begin(),addi.end());
            r2 += *x;
        }
        return dp[x][m] = r + max(r2,0);
    }
    else{
        int ret = 0;
        int addi = 0;
        for(pi i : graph[x]){
            if(i.second == pa) continue;
            int classic = max(f(i.second,0,x,i.first),f(i.second,1,x,i.first));
            int pick = f(i.second,0,x,i.first) + i.first + e;
            ret += classic;
            addi = max(addi,pick - classic);
        }
        return dp[x][m] = ret + addi;
    }
}

int main(){
    memset(dp,-1,sizeof(dp));
    scanf("%d",&n);
    for (int i=0; i<n-1; i++) {
        int s,e,x;
        scanf("%d %d %d",&s,&e,&x);
        graph[s].push_back(pi(x,e));
        graph[e].push_back(pi(x,s));
    }
    printf("%d",f(1,0,0,0));
}

Compilation message

beads.cpp: In function 'int f(int, int, int, int)':
beads.cpp:18:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<graph[x].size(); i++) {
                       ~^~~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
beads.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&s,&e,&x);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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