# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
235531 | 2020-05-28T12:41:27 Z | Autoratch | 구슬과 끈 (APIO14_beads) | C++14 | 8 ms | 5120 KB |
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 1; int n; vector<pair<int,int> > adj[N]; int a[N][4]; void dfs(int u,int p) { a[u][1] = INT_MIN; a[u][3] = INT_MIN; int m3 = INT_MIN,m21 = INT_MIN,m22 = INT_MIN,m01 = INT_MIN,m02 = INT_MIN,v2,v0; int ed = 0,lft = 0; for(auto [d,v] : adj[u]) if(v!=p) { dfs(v,u); int each = max(a[v][0],a[v][2]); lft+=each; if(a[v][1]!=INT_MIN) a[u][0]+=a[v][1]+d-each; if(a[v][1]==INT_MIN) a[u][1] = max(a[u][1],a[v][0]+d-each); else a[u][1] = max(a[u][1],a[v][0]-a[v][1]); if(a[v][3]!=INT_MIN) { if(a[v][1]==INT_MIN) m3 = max(m3,a[v][3]+d-each); else m3 = max(m3,a[v][3]-a[v][1]); } if(a[v][1]==INT_MIN) { if(a[v][2]+d-each>m21) m22 = m21,m21 = a[v][2]+d-each,v2 = v; else if(a[v][2]+d-each>m22) m22 = a[v][2]+d-each; } else { if(a[v][2]-a[v][1]>m21) m22 = m21,m21 = a[v][2]-a[v][1],v2 = v; else if(a[v][2]-a[v][1]>m22) m22 = a[v][2]-a[v][1]; } if(a[v][1]==INT_MIN) { if(a[v][0]+d-each>m01) m02 = m01,m01 = a[v][0]+d-each,v0 = v; else if(a[v][0]+d-each>m02) m02 = a[v][0]+d-each; } else { if(a[v][0]-a[v][1]>m01) m02 = m01,m01 = a[v][0]-a[v][1],v0 = v; else if(a[v][0]-a[v][1]>m02) m02 = a[v][0]-a[v][1]; } if(a[v][1]==INT_MIN) a[u][3] = max(a[u][3],a[v][2]+d-each); else a[u][3] = max(a[u][3],a[v][2]-a[v][1]); /* if(u==1) { cout << a[v][0] << ' ' << a[v][1] << ' ' << a[v][2] << ' ' << d << ' ' << each << endl; cout << v0 << ' ' << m01 << endl; cout << v2 << ' ' << m21 << endl; } */ } a[u][0]+=lft; if(a[u][1]!=INT_MIN) a[u][1]+=a[u][0]; if(a[u][3]!=INT_MIN) a[u][3]+=a[u][0]; if(m01!=INT_MIN and m02!=INT_MIN) a[u][2] = max(a[u][2],a[u][0]+m01+m02); if(m01!=INT_MIN and m21!=INT_MIN and v2!=v0) a[u][2] = max(a[u][2],a[u][0]+m01+m21); if(m02!=INT_MIN and m21!=INT_MIN) a[u][2] = max(a[u][2],a[u][0]+m02+m21); if(m01!=INT_MIN and m22!=INT_MIN) a[u][2] = max(a[u][2],a[u][0]+m01+m22); if(m3!=INT_MIN) a[u][2] = max(a[u][2],m3+a[u][0]); /* if(u==1) { cout << m01 << ' ' << m02 << ' ' << m21 << ' ' << m22 << endl; } cout << u << ' ' << lft << endl; for(int i = 0;i < 4;i++) cout << a[u][i] << ' '; cout << endl; */ } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = 0;i < n-1;i++) { int a,b,d; cin >> a >> b >> d; adj[a].push_back({d,b}); adj[b].push_back({d,a}); } dfs(1,0); cout << max(a[1][0],a[1][2]); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 4992 KB | Output is correct |
2 | Correct | 8 ms | 4992 KB | Output is correct |
3 | Correct | 7 ms | 4992 KB | Output is correct |
4 | Correct | 7 ms | 5120 KB | Output is correct |
5 | Correct | 7 ms | 4992 KB | Output is correct |
6 | Correct | 7 ms | 5120 KB | Output is correct |
7 | Incorrect | 7 ms | 4992 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 4992 KB | Output is correct |
2 | Correct | 8 ms | 4992 KB | Output is correct |
3 | Correct | 7 ms | 4992 KB | Output is correct |
4 | Correct | 7 ms | 5120 KB | Output is correct |
5 | Correct | 7 ms | 4992 KB | Output is correct |
6 | Correct | 7 ms | 5120 KB | Output is correct |
7 | Incorrect | 7 ms | 4992 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 4992 KB | Output is correct |
2 | Correct | 8 ms | 4992 KB | Output is correct |
3 | Correct | 7 ms | 4992 KB | Output is correct |
4 | Correct | 7 ms | 5120 KB | Output is correct |
5 | Correct | 7 ms | 4992 KB | Output is correct |
6 | Correct | 7 ms | 5120 KB | Output is correct |
7 | Incorrect | 7 ms | 4992 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 4992 KB | Output is correct |
2 | Correct | 8 ms | 4992 KB | Output is correct |
3 | Correct | 7 ms | 4992 KB | Output is correct |
4 | Correct | 7 ms | 5120 KB | Output is correct |
5 | Correct | 7 ms | 4992 KB | Output is correct |
6 | Correct | 7 ms | 5120 KB | Output is correct |
7 | Incorrect | 7 ms | 4992 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |