제출 #670154

#제출 시각아이디문제언어결과실행 시간메모리
670154radal구슬과 끈 (APIO14_beads)C++17
57 / 100
908 ms7504 KiB
#include <bits/stdc++.h> #pragma GCC target("sse,sse2,avx2") #pragma GCC optimize("unroll-loops,O2") #define rep(i,l,r) for (int i = l; i < r; i++) #define repr(i,r,l) for (int i = r; i >= l; i--) #define X first #define Y second #define all(x) (x).begin() , (x).end() #define pb push_back #define endl '\n' #define debug(x) cerr << #x << " : " << x << endl; using namespace std; typedef long long ll; typedef pair<int,int> pll; constexpr int N = 2e5+10,mod = 1e9+7,maxm = 210; constexpr ll inf = 1e9+10; inline int mkay(int a,int b){ if (a+b >= mod) return a+b-mod; // if (a+b < 0) return a+b+mod; return a+b; } inline int poww(int a,int k){ if (k < 0) return 0; int z = 1; while (k){ if (k&1) z = 1ll*z*a%mod; a = 1ll*a*a%mod; k >>= 1; } return z; } vector<pll> adj[N]; int dp[N][2]; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void dfs(int v,int p){ if ((int) adj[v].size() == 1 && p != 0){ dp[v][1] = -2*inf; dp[v][0] = 0; return; } int s = 0,mx = -2*inf; for (auto [u,w] : adj[v]){ if (u == p) continue; dfs(u,v); int val = max(dp[u][0],dp[u][1]+w); s += val; mx = max(mx,dp[u][0]-val+w); } dp[v][0] = s; dp[v][1] = s + mx; } bool cmp(int i,int j){ return adj[i][0].Y > adj[j][0].Y; } int main(){ ios :: sync_with_stdio(0); cin.tie(0); int n; cin >> n; int mx = -1,U = -1,V = -1; rep(i,1,n){ int u,v,w; cin >> u >> v >> w; if (w > mx){ mx = w; U = u; V = v; } adj[u].pb({v,w}); adj[v].pb({u,w}); } if (n <= 2){ cout << 0 << endl; return 0; } vector<int> leaf; rep(i,1,n+1){ if ((int)adj[i].size() == 1){ leaf.pb(i); leaf.pb(adj[i][0].X); } } sort(all(leaf)); leaf.resize(unique(all(leaf))-leaf.begin()); sort(all(leaf),cmp); // shuffle(all(leaf),rng); int t = min(30000000/n,(int)leaf.size()),ans = 0; rep(i,0,t){ dfs(leaf[i],0); ans = max(ans,dp[leaf[i]][0]); } dfs(U,0); ans = max(ans,dp[U][0]); dfs(V,0); ans = max(ans,dp[V][0]); cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...