oj.uz

Submission #154547

# Submission time Handle Problem Language Result Execution time Memory
154547 2019-09-22T15:55:40 Z pink_bittern Beads and wires (APIO14_beads) C++14
0 / 100
 8 ms 7416 KB 
#include <bits/stdc++.h>
#include <complex>
#define pb push_back
#define pll pair <ll, ll>
#define MOMI using namespace std;
#define mp make_pair
#define pyshnapyshnakaa ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#pragma optimize("TKACHENKO-GORYACHENKO")
#pragma GCC optimize("O3")

//#pragma GCC optimize("unroll-loops")
//#define double long double

typedef long long ll;

typedef long double ld;

using namespace std;

const ll maxn = 300000;
const ll inf = 1e15;

struct edge{
    ll to;
    ll c;
};

ll n, m, k;

ll D[maxn][3];

//ll C[maxn];

vector <edge> V[maxn];

void dfs(ll v, ll p, ll c){
    ll q;
    ll s = 0;
    for (q = 0; q < V[v].size(); q++){
        ll v1 = V[v][q].to;
        if (v1 == p){
            continue;
        }
        dfs(v1, v, V[v][q].c);
        s += D[v1][1];
    }
    ll mx1 = -inf;
    for (q = 0; q < V[v].size(); q++){
        ll v1 = V[v][q].to;
        if (v1 == p){
            continue;
        }
        mx1 = max(mx1, D[v1][0] - D[v1][1] + V[v][q].c);
    }
    ll mx2 = -inf, mx3 = -inf, mx2i = 0, mx3i = 0;
    for (q = 0; q < V[v].size(); q++){
        ll v1 = V[v][q].to;
        if (v1 == p){
            continue;
        }
        ll dmx = D[v1][2] - D[v1][1] + V[v][q].c;
        if (dmx > mx2){
            mx3 = mx2;
            mx3i = mx2i;
            mx2 = dmx;
            mx2i = q;
            continue;
        }
        if (dmx > mx3){
            mx3 = dmx;
            mx3i = q;
        }
    }
    ll sum1 = -inf, sum2 = -inf;
    for (q = 0; q < V[v].size(); q++){
        ll v1 = V[v][q].to;
        if (v1 == p){
            continue;
        }
        if (q == mx2i){
            continue;
        }
        ll dsum = mx2 + D[v1][0] - D[v1][1] + V[v][q].c;
        sum1 = max(sum1, dsum);
    }
    for (q = 0; q < V[v].size(); q++){
        ll v1 = V[v][q].to;
        if (v1 == p){
            continue;
        }
        if (q == mx3i){
            continue;
        }
        ll dsum = mx3 + D[v1][0] - D[v1][1] + V[v][q].c;
        sum1 = max(sum1, dsum);
    }
//    cout << "SUM " << sum1 << endl;
    D[v][0] = max(D[v][0] + s, D[v][0]);
    D[v][2] = max(D[v][0], s + sum1);
    D[v][1] = max(max(D[v][1], D[v][2]), s + mx1 + c);
//    cout << "V " << v << " " << "D " << D[v][0] << " " << D[v][1] << " " << D[v][2] << endl;
}

int main(){
    ll q, w, e, t, a, b, c;
    cin >> n;
    for (q = 0; q < n - 1; q++){
        cin >> a >> b >> c;
        a--; b--;
        edge e, f;
        e.to = b; f.to = a;
        e.c = f.c = c;
        V[a].pb(e); V[b].pb(f);
//        C[a] += c; C[b] += c;
    }
//    cout << "END " << endl;
    dfs(0, 0, -inf);
    cout << D[0][1];
    return 0;
}

Compilation message

beads.cpp:8:0: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
 #pragma optimize("TKACHENKO-GORYACHENKO")
 
beads.cpp: In function 'void dfs(ll, ll, ll)':
beads.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (q = 0; q < V[v].size(); q++){
                 ~~^~~~~~~~~~~~~
beads.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (q = 0; q < V[v].size(); q++){
                 ~~^~~~~~~~~~~~~
beads.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (q = 0; q < V[v].size(); q++){
                 ~~^~~~~~~~~~~~~
beads.cpp:75:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (q = 0; q < V[v].size(); q++){
                 ~~^~~~~~~~~~~~~
beads.cpp:86:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (q = 0; q < V[v].size(); q++){
                 ~~^~~~~~~~~~~~~
beads.cpp:74:21: warning: unused variable 'sum2' [-Wunused-variable]
     ll sum1 = -inf, sum2 = -inf;
                     ^~~~
beads.cpp: In function 'int main()':
beads.cpp:105:11: warning: unused variable 'w' [-Wunused-variable]
     ll q, w, e, t, a, b, c;
           ^
beads.cpp:105:14: warning: unused variable 'e' [-Wunused-variable]
     ll q, w, e, t, a, b, c;
              ^
beads.cpp:105:17: warning: unused variable 't' [-Wunused-variable]
     ll q, w, e, t, a, b, c;
                 ^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Incorrect 8 ms 7416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Incorrect 8 ms 7416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Incorrect 8 ms 7416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Incorrect 8 ms 7416 KB Output isn't correct
4 Halted 0 ms 0 KB -