Submission #152552

#	Time	Username	Problem	Language	Result	Execution time	Memory
152552		pink_bittern	Beads and wires (APIO14_beads)	C++14	0 / 100	9 ms	7544 KiB

beads

#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 (stderr)

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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43