제출 #554204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554204		kwongweng	구슬과 끈 (APIO14_beads)	C++17	100 / 100	272 ms	34792 KiB

beads

/*
Solution for APIO 2014 - Beads
Tags : Tree dp, Solving for all roots
*/

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
 
ll MOD = 1000000007;
 
ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}
 
ll add(ll a, ll b){
	return (a+b) % MOD;
}
 
ll mul(ll a, ll b){
	a %= MOD;
	return (a*b) % MOD;
}
 
ll gcd(ll a, ll b){
    if (a == 1) return 1;
    if (a == 0) return b;
    return gcd(b%a, a);
}
 
const int N = 200001;
vii g[N];
int dp[N][2];
vi ans(N);
vi val(N);
//dp[i][0] = answer for subtree rooted at i
//dp[i][1] = same answer, with edge (i, some child) removed
// this edge is to be paired with edge (i parent of i)

//computing answer when root is 1
void dfs(int u, int p){
    dp[u][0]=0; dp[u][1]=-MOD;
    int sz = 0;
    for (ii edge : g[u]){
        int v = edge.fi; int w = edge.se;
        if (v==p) continue;
        sz++;
        dfs(v,u);
        dp[u][0] += max(dp[v][0], dp[v][1]+w);
    }
    if (sz==0){
        return;
    }
    for (ii edge : g[u]){
        int v = edge.fi, w = edge.se;
        if (v==p) continue;
        int val = dp[v][0]+w - max(dp[v][0], dp[v][1]+w);
        dp[u][1] = max(dp[u][1], dp[u][0]+val);
        // This is when edge(u,v) is paired with edge(u,p)
    }
}

//Solving for all roots
void dfs2(int u, int p, int W){
    multiset<int> st; int sz=0;
    for (ii edge : g[u]){
        int v = edge.fi; int w = edge.se;
        if (v==p) continue;
        
        val[v]=dp[v][0] + w - max(dp[v][0], dp[v][1]+w);
        st.insert(val[v]);
        sz++;
        ans[v]=max(ans[v], ans[u] + dp[u][0]-max(dp[v][0], dp[v][1]+w));
        //edge (u,v) not used
 
        if (p==0) continue;
        int val1 = ans[p]+dp[p][0]-max(dp[u][0],dp[u][1]+W);
        int val2 = W+w + dp[u][0] - max(dp[v][0], dp[v][1]+w);
        //edge (u,v) paired with (u,p)
        ans[v]=max(ans[v], val1+val2);
    }
    
    //edge (u,v) paired with (u,v'), v' another child of u
    for (ii edge : g[u]){
        int v = edge.fi; int w =edge.se;
        if (v==p || sz < 2) continue;
        st.erase(st.find(val[v]));
        int val1 = dp[u][0]+val[v]-dp[v][0];
        val1 = ans[u] + val1 + *st.rbegin();
        ans[v]=max(ans[v], val1);
        st.insert(val[v]);
    }
    
    for (ii edge : g[u]){
        int v = edge.fi; int w = edge.se;
        if (v==p) continue;
        dfs2(v,u,w);
    }
}
 
void solve(){
    int n; cin >> n;
    FOR(i,0,n-1){
        int u,v,w; cin>>u>>v>>w;
        g[u].pb({v,w}); g[v].pb({u,w});
    }
    dfs(1,0);
    dfs2(1,0,-MOD);
    int answer = 0;
    FOR(i,1,n+1){
        ans[i]+=dp[i][0]; //answer if starting bead is i
        answer=max(answer, ans[i]);
    }
    cout << answer <<'\n';
    return;
}
 
int main() {
    ios::sync_with_stdio(false);
    int TC = 1;
    //cin >> TC;
    FOR(i, 1, TC+1){
        //cout << "Case #" << i << ": ";
        solve();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

beads.cpp:10: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   10 | #pragma GCC optimization ("Ofast")
      | 
beads.cpp:11: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   11 | #pragma GCC optimization ("unroll-loops")
      | 
beads.cpp: In function 'void dfs2(int, int, int)':
beads.cpp:109:30: warning: unused variable 'w' [-Wunused-variable]
  109 |         int v = edge.fi; int w =edge.se;
      |                              ^

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