Submission #940847

#	Time	Username	Problem	Language	Result	Execution time	Memory
940847		sysia	Beads and wires (APIO14_beads)	C++17	100 / 100	163 ms	38080 KiB

beads

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

void solve(){
    int n; cin >> n;
    vector<vector<T>>g(n+1);
    for (int i = 1; i<n; i++){
        int a, b, c; cin >> a >> b >> c;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    //pomiedzy kazda para wisienek sciezka laczaca ich srodki musi przechodzic przez inny wierzcholek jakiejs wisienki jeszcze
    //dp[v][0] -> jest wisienka w poddrzewie, nie uzywamy krawedzi do rodzica
    //dp[v][1] -> jest wisienka w poddrzewie, uzywamy krawedzi do rodzica
    //dp[v][2] -> nie ma wisienki w poddrzewie, nie uzywamy krawedzi do rodzica
    //dp[v][3] -> nie ma wisienki w poddrzewie, uzywamy krawedz do rodzica
    vector dp(n+1, vector<int>(4));
    function<void(int, int, int)>dfs = [&](int v, int pa, int cc){
        for (auto [x, c]: g[v]){
            if (x == pa) continue;
            dfs(x, v, c);
            dp[v][2] += max(dp[x][2], dp[x][3]);
        }
        for (auto [x, c]: g[v]){
            dp[v][0] = max(dp[v][0], dp[v][2]+max(dp[x][0], dp[x][1])-max(dp[x][2], dp[x][3]));
        }
        //dp[v][0] -> robimy wisienke w wierzcholku v -> maksymalnie jeden syn wisienki moze miec dp[x][0]
        //dp[v][0] = dp[v][2] + [dp[x][0] - max(dp[x][2], dp[x][3]) + c1] + [dp[x][2]-max(dp[x][2], dp[x][3]) + c2]        
        
        //dp[v][1] -> 1) dp[v][2] + [dp[x][0] - max(dp[x][2], dp[x][3]) + c] + cc (gdy ta jedna wisienka w poddrzewie x)
        //lub dp[v][2] + [dp[x][2] - max(dp[x][2], dp[x][3]) + c] + cc + [max(dp[x][0], dp[x][1]) - max(dp[x][2], dp[x][3])];
        vector<T>mx(2, {-oo, -oo});
        for (auto [x2, c2]: g[v]){
            if (x2 == pa) continue;
            T val = {dp[x2][2]-max(dp[x2][2], dp[x2][3]) + c2, x2};
            if (val >= mx[0]) swap(val, mx[0]);
            if (val >= mx[1]) swap(val, mx[1]);
        }
        for (auto [x1, c1]: g[v]){
            if (x1 == pa) continue;
            dp[v][1] = max(dp[v][1], dp[v][2] + (dp[x1][0] - max(dp[x1][2], dp[x1][3]) + c1) + cc);
            dp[v][0] = max(dp[v][0], 
                dp[v][2] + (dp[x1][0] - max(dp[x1][2], dp[x1][3]) +c1) + (mx[0].second == x1 ? mx[1].first : mx[0].first));
            // for (auto [x2, c2]: g[v]){
                // if (x2 == pa || x2 == x1) continue;
                
                //tu uzywam tego rozroznienia zeby moc uzyc faktu ze nie ma krawedzi do rodzica
                // dp[v][1] = max(dp[v][1], 
                // dp[v][2] + (dp[x1][2] - max(dp[x1][2], dp[x1][3]) + c1) + cc + (max(dp[x2][0], dp[x2][1]) - max(dp[x2][2], dp[x2][3]))); -> nie moge tego uzyc bo powstaje polaczenie pomiedzy srodkami pionowej i w poddrzewie wisienki
            // }
        }
        //dp[v][3] = dp[v][2] + cc + [dp[x][2] - max(dp[x][2], dp[x][3]) + c]
        for (auto [x, c]: g[v]){
            if (x == pa) continue;
            dp[v][3] = max(dp[v][3], dp[v][2]+cc+dp[x][2]-max(dp[x][2], dp[x][3])+c);
        }
        debug(v, dp[v]);
    };
    dfs(1, 1, -oo);    
    cout << max(dp[1][0], dp[1][2]) << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43