oj.uz

Submission #114231

# Submission time Handle Problem Language Result Execution time Memory
114231 2019-05-31T11:43:01 Z patrikpavic2 Beads and wires (APIO14_beads) C++17
0 / 100
 19 ms 16000 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef pair < int, int > pii;
typedef vector < pii > vp;
typedef long long ll;

const int N = 5e5 + 500;
const int INF = 0x3f3f3f3f;

vp v[N];
int n;
int dp[N][2];

int f(int x,int k,int lst,int can = 0){
    if(v[x].size() == (x != 1)) return (k == 1) * (-INF);
    //if(dp[x][k] != -1) return dp[x][k];
    int m0 = 0, m1 = -INF , m2 = -INF, m0_can = -INF, m1_can = -INF, m2_can = -INF;
    for(pii A : v[x]){
        int nxt = A.X, tez = A.Y;
        if(nxt == lst) continue;
        int op1 = f(nxt, 0, x);
        int op2 = f(nxt, 1, x);

        int ob = max(op1, op2 + tez);
        //printf("X : %d nxt : %d op1 : )
        if(can) {
            int op21 = f(nxt, 0, x, 1);
            int op22 = f(nxt, 1, x, 1);
            int ob2 = max(op21, op22 + tez);
            m2_can = max(max(m2_can + ob, m1 + op21 + tez), max(m2 + ob2, m1_can + op1 + tez));
            m1_can = max(max(m1_can + ob, m0 + op21 + tez), m1 + ob2);
            m0_can = max(m0_can + ob, m0 + ob2);
        }
        m2 = max(m2 + ob, m1 + op1 + tez);
        m1 = max(m1 + ob, m0 + op1 + tez);
        m0 += ob;
        //m1 = max(m1, -INF); m2 = max(m2, -INF);
    }
    //printf("X = %d %lld %lld %lld\n", x, m0, m1, m2);
    if(k == 1)
        return dp[x][k] = max(m1, can * m1_can);
    //if(x == 2) printf("m2 %d m0 %d %d\n", m2_can, m0,  k, can);
    return dp[x][k] = max(max(m0, m0_can * can), can * max(m2_can, m2));
}

int main(){
    scanf("%d", &n);
    for(int i = 1;i < n;i++){
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        v[x].PB({y, z});
        v[y].PB({x, z});
    }
    memset(dp, -1, sizeof(dp));
    printf("%d\n", f(1, 0, 1, 1));
}

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:58:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x, y, z; scanf("%d%d%d", &x, &y, &z);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16000 KB Output is correct
2 Correct 15 ms 16000 KB Output is correct
3 Correct 16 ms 16000 KB Output is correct
4 Correct 16 ms 16000 KB Output is correct
5 Correct 16 ms 16000 KB Output is correct
6 Correct 16 ms 15976 KB Output is correct
7 Incorrect 19 ms 16000 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16000 KB Output is correct
2 Correct 15 ms 16000 KB Output is correct
3 Correct 16 ms 16000 KB Output is correct
4 Correct 16 ms 16000 KB Output is correct
5 Correct 16 ms 16000 KB Output is correct
6 Correct 16 ms 15976 KB Output is correct
7 Incorrect 19 ms 16000 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16000 KB Output is correct
2 Correct 15 ms 16000 KB Output is correct
3 Correct 16 ms 16000 KB Output is correct
4 Correct 16 ms 16000 KB Output is correct
5 Correct 16 ms 16000 KB Output is correct
6 Correct 16 ms 15976 KB Output is correct
7 Incorrect 19 ms 16000 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16000 KB Output is correct
2 Correct 15 ms 16000 KB Output is correct
3 Correct 16 ms 16000 KB Output is correct
4 Correct 16 ms 16000 KB Output is correct
5 Correct 16 ms 16000 KB Output is correct
6 Correct 16 ms 15976 KB Output is correct
7 Incorrect 19 ms 16000 KB Output isn't correct
8 Halted 0 ms 0 KB -