# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
409006 | 2021-05-20T03:57:02 Z | TLP39 | 구슬과 끈 (APIO14_beads) | C++14 | 4 ms | 5004 KB |
#include<bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int,int> pii; int n; int ans[200010][2]; int par[200010]; int distpar[200010]; vector<pii> adj[200010]; void dfs(int v) { for(int i=0;i<adj[v].size();i++) { if(par[v]==adj[v][i].first) continue; par[adj[v][i].first]=v; distpar[adj[v][i].first]=adj[v][i].second; dfs(adj[v][i].first); } } void init() { scanf("%d",&n); int a,b,c; for(int i=1;i<n;i++) { scanf("%d %d %d",&a,&b,&c); adj[a].push_back({b,c}); adj[b].push_back({a,c}); } par[1]=0; distpar[1]=-1000000; dfs(1); } void solve(int v) { ans[v][0]=0; ans[v][1]=0; if(adj[v].size()==1 && v!=1) return; if(adj[v].size()-(v!=1)==1) { int temp=adj[v][0].first; if(temp==par[v]) temp=adj[v][1].first; ans[v][0]=ans[temp][1]; if(v!=1) ans[v][1]=max(ans[v][0],distpar[v]+distpar[temp]+ans[temp][0]); return; } int tot=0; for(int i=0;i<adj[v].size();i++) { if(adj[v][i].first==par[v]) continue; tot+=ans[adj[v][i].first][1]; } int ma[2]={-1000000,-1000000},hold; for(int i=0;i<adj[v].size();i++) { if(adj[v][i].first==par[v]) continue; hold=adj[v][i].second+ans[adj[v][i].first][0]-ans[adj[v][i].first][1]; if(hold>ma[0]) { ma[1]=ma[0]; ma[0]=hold; } else if(hold>ma[1]) ma[1]=hold; } ans[v][0]=tot+max(0,ma[0]+ma[1]); if(v==1) return; ans[v][1]=max(ans[v][0],distpar[v]+ma[0]+tot); return; } void dp_solve() { queue<int> q; int deg[n+1]; for(int i=1;i<=n;i++) { deg[i]=adj[i].size()-(i!=1); if(deg[i]==0) q.push(i); } int fr; while(!q.empty()) { fr=q.front(); q.pop(); solve(fr); deg[par[fr]]--; if(!deg[par[fr]]) q.push(par[fr]); } } int main() { init(); dp_solve(); printf("%d",ans[1][0]); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4940 KB | Output is correct |
2 | Correct | 4 ms | 4940 KB | Output is correct |
3 | Correct | 3 ms | 4940 KB | Output is correct |
4 | Correct | 4 ms | 5004 KB | Output is correct |
5 | Correct | 4 ms | 5000 KB | Output is correct |
6 | Incorrect | 4 ms | 4940 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4940 KB | Output is correct |
2 | Correct | 4 ms | 4940 KB | Output is correct |
3 | Correct | 3 ms | 4940 KB | Output is correct |
4 | Correct | 4 ms | 5004 KB | Output is correct |
5 | Correct | 4 ms | 5000 KB | Output is correct |
6 | Incorrect | 4 ms | 4940 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4940 KB | Output is correct |
2 | Correct | 4 ms | 4940 KB | Output is correct |
3 | Correct | 3 ms | 4940 KB | Output is correct |
4 | Correct | 4 ms | 5004 KB | Output is correct |
5 | Correct | 4 ms | 5000 KB | Output is correct |
6 | Incorrect | 4 ms | 4940 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4940 KB | Output is correct |
2 | Correct | 4 ms | 4940 KB | Output is correct |
3 | Correct | 3 ms | 4940 KB | Output is correct |
4 | Correct | 4 ms | 5004 KB | Output is correct |
5 | Correct | 4 ms | 5000 KB | Output is correct |
6 | Incorrect | 4 ms | 4940 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |