oj.uz

Submission #114232

# Submission time Handle Problem Language Result Execution time Memory
114232 2019-05-31T11:48:38 Z patrikpavic2 Beads and wires (APIO14_beads) C++17
13 / 100
 62 ms 16052 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstdlib>
#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, root;
int dp[N][2];

int f(int x,int k,int lst,int can = 0){
    if(v[x].size() == (x != root)) 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));
    int ans = INF;
    for(int j = 0;j < 20;j++){
        root = rand() % n + 1;
        ans = min(ans, f(root, 0, root, 1));
    }
    printf("%d\n", ans);
}

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:59: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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16000 KB Output is correct
2 Correct 16 ms 16000 KB Output is correct
3 Correct 15 ms 16000 KB Output is correct
4 Correct 15 ms 16000 KB Output is correct
5 Correct 17 ms 15992 KB Output is correct
6 Correct 16 ms 16000 KB Output is correct
7 Correct 16 ms 16000 KB Output is correct
8 Correct 15 ms 16000 KB Output is correct
9 Correct 16 ms 15968 KB Output is correct
10 Correct 14 ms 16000 KB Output is correct
11 Correct 16 ms 16000 KB Output is correct
12 Correct 16 ms 16000 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16000 KB Output is correct
2 Correct 16 ms 16000 KB Output is correct
3 Correct 15 ms 16000 KB Output is correct
4 Correct 15 ms 16000 KB Output is correct
5 Correct 17 ms 15992 KB Output is correct
6 Correct 16 ms 16000 KB Output is correct
7 Correct 16 ms 16000 KB Output is correct
8 Correct 15 ms 16000 KB Output is correct
9 Correct 16 ms 15968 KB Output is correct
10 Correct 14 ms 16000 KB Output is correct
11 Correct 16 ms 16000 KB Output is correct
12 Correct 16 ms 16000 KB Output is correct
13 Correct 36 ms 16000 KB Output is correct
14 Incorrect 62 ms 16052 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16000 KB Output is correct
2 Correct 16 ms 16000 KB Output is correct
3 Correct 15 ms 16000 KB Output is correct
4 Correct 15 ms 16000 KB Output is correct
5 Correct 17 ms 15992 KB Output is correct
6 Correct 16 ms 16000 KB Output is correct
7 Correct 16 ms 16000 KB Output is correct
8 Correct 15 ms 16000 KB Output is correct
9 Correct 16 ms 15968 KB Output is correct
10 Correct 14 ms 16000 KB Output is correct
11 Correct 16 ms 16000 KB Output is correct
12 Correct 16 ms 16000 KB Output is correct
13 Correct 36 ms 16000 KB Output is correct
14 Incorrect 62 ms 16052 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16000 KB Output is correct
2 Correct 16 ms 16000 KB Output is correct
3 Correct 15 ms 16000 KB Output is correct
4 Correct 15 ms 16000 KB Output is correct
5 Correct 17 ms 15992 KB Output is correct
6 Correct 16 ms 16000 KB Output is correct
7 Correct 16 ms 16000 KB Output is correct
8 Correct 15 ms 16000 KB Output is correct
9 Correct 16 ms 15968 KB Output is correct
10 Correct 14 ms 16000 KB Output is correct
11 Correct 16 ms 16000 KB Output is correct
12 Correct 16 ms 16000 KB Output is correct
13 Correct 36 ms 16000 KB Output is correct
14 Incorrect 62 ms 16052 KB Output isn't correct
15 Halted 0 ms 0 KB -