oj.uz

Submission #152552

# Submission time Handle Problem Language Result Execution time Memory
152552 2019-09-08T11:47:23 Z pink_bittern Beads and wires (APIO14_beads) C++14
0 / 100
 9 ms 7544 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][2];

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, mx2 = -inf;
    for (q = 0; q < V[v].size(); q++){
        ll v1 = V[v][q].to;
        if (v1 == p){
            continue;
        }
        ll dmx = D[v1][0] + V[v][q].c - D[v1][1];
        if (mx1 < dmx){
            mx2 = mx1;
            mx1 = dmx;
            continue;
        }
        if (mx2 < dmx){
            mx2 = dmx;
        }
    }
    D[v][0] = max(D[v][0], s + mx1 + mx2);
    D[v][1] = max(max(D[v][1], D[v][0]), s + mx1 + c);
}

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][0];
    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: In function 'int main()':
beads.cpp:68:11: warning: unused variable 'w' [-Wunused-variable]
     ll q, w, e, t, a, b, c;
           ^
beads.cpp:68:14: warning: unused variable 'e' [-Wunused-variable]
     ll q, w, e, t, a, b, c;
              ^
beads.cpp:68: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 9 ms 7544 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 9 ms 7544 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 9 ms 7544 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 9 ms 7544 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 -