# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
580920 | 2022-06-22T06:19:17 Z | 조영욱(#8362) | Beads and wires (APIO14_beads) | C++17 | 1000 ms | 10252 KB |
#include <bits/stdc++.h> using namespace std; int n; typedef pair<int,int> P; vector<P> adj[200001]; long long dp[200001][2]; vector<P> son[200001]; const long long nnn=-1e16; const long long nn=-1e12-7; void dfs(int v,int prev) { for(int i=0;i<adj[v].size();i++) { P nt=adj[v][i]; if (nt.first!=prev) { son[v].push_back(nt); dfs(nt.first,v); } } } long long ans(int v,int type) { if (dp[v][type]!=nnn) { return dp[v][type]; } if (type==0) { long long ret=0; long long mx=0; for(int i=0;i<son[v].size();i++) { ret+=max(ans(son[v][i].first,0),ans(son[v][i].first,1)+son[v][i].second); } return dp[v][type]=ret+mx; } if (type==1) { long long ret=0; long long mx=nn; for(int i=0;i<son[v].size();i++) { ret+=max(ans(son[v][i].first,0),ans(son[v][i].first,1)+son[v][i].second); mx=max(mx,ans(son[v][i].first,0)+son[v][i].second-max(ans(son[v][i].first,0),ans(son[v][i].first,1)+son[v][i].second)); } return dp[v][type]=ret+mx; } } int main(void) { scanf("%d",&n); for(int i=1;i<n;i++) { int u,v,w; scanf("%d %d %d",&u,&v,&w); u--; v--; adj[u].push_back(P(v,w)); adj[v].push_back(P(u,w)); } long long ret=0; for(int r=0;r<n;r++) { for(int i=0;i<n;i++) { son[i].clear(); dp[i][0]=nnn; dp[i][1]=nnn; } dfs(r,-1); ret=max(ret,ans(r,0)); } printf("%lld",ret); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 9684 KB | Output is correct |
2 | Correct | 6 ms | 9684 KB | Output is correct |
3 | Correct | 6 ms | 9684 KB | Output is correct |
4 | Correct | 5 ms | 9684 KB | Output is correct |
5 | Correct | 5 ms | 9684 KB | Output is correct |
6 | Correct | 5 ms | 9684 KB | Output is correct |
7 | Correct | 5 ms | 9708 KB | Output is correct |
8 | Correct | 6 ms | 9684 KB | Output is correct |
9 | Correct | 6 ms | 9712 KB | Output is correct |
10 | Correct | 7 ms | 9684 KB | Output is correct |
11 | Correct | 7 ms | 9684 KB | Output is correct |
12 | Correct | 7 ms | 9636 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 9684 KB | Output is correct |
2 | Correct | 6 ms | 9684 KB | Output is correct |
3 | Correct | 6 ms | 9684 KB | Output is correct |
4 | Correct | 5 ms | 9684 KB | Output is correct |
5 | Correct | 5 ms | 9684 KB | Output is correct |
6 | Correct | 5 ms | 9684 KB | Output is correct |
7 | Correct | 5 ms | 9708 KB | Output is correct |
8 | Correct | 6 ms | 9684 KB | Output is correct |
9 | Correct | 6 ms | 9712 KB | Output is correct |
10 | Correct | 7 ms | 9684 KB | Output is correct |
11 | Correct | 7 ms | 9684 KB | Output is correct |
12 | Correct | 7 ms | 9636 KB | Output is correct |
13 | Correct | 6 ms | 9684 KB | Output is correct |
14 | Correct | 6 ms | 9704 KB | Output is correct |
15 | Correct | 7 ms | 9684 KB | Output is correct |
16 | Correct | 9 ms | 9684 KB | Output is correct |
17 | Correct | 8 ms | 9684 KB | Output is correct |
18 | Correct | 7 ms | 9708 KB | Output is correct |
19 | Correct | 8 ms | 9684 KB | Output is correct |
20 | Correct | 9 ms | 9684 KB | Output is correct |
21 | Correct | 7 ms | 9724 KB | Output is correct |
22 | Correct | 7 ms | 9684 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 9684 KB | Output is correct |
2 | Correct | 6 ms | 9684 KB | Output is correct |
3 | Correct | 6 ms | 9684 KB | Output is correct |
4 | Correct | 5 ms | 9684 KB | Output is correct |
5 | Correct | 5 ms | 9684 KB | Output is correct |
6 | Correct | 5 ms | 9684 KB | Output is correct |
7 | Correct | 5 ms | 9708 KB | Output is correct |
8 | Correct | 6 ms | 9684 KB | Output is correct |
9 | Correct | 6 ms | 9712 KB | Output is correct |
10 | Correct | 7 ms | 9684 KB | Output is correct |
11 | Correct | 7 ms | 9684 KB | Output is correct |
12 | Correct | 7 ms | 9636 KB | Output is correct |
13 | Correct | 6 ms | 9684 KB | Output is correct |
14 | Correct | 6 ms | 9704 KB | Output is correct |
15 | Correct | 7 ms | 9684 KB | Output is correct |
16 | Correct | 9 ms | 9684 KB | Output is correct |
17 | Correct | 8 ms | 9684 KB | Output is correct |
18 | Correct | 7 ms | 9708 KB | Output is correct |
19 | Correct | 8 ms | 9684 KB | Output is correct |
20 | Correct | 9 ms | 9684 KB | Output is correct |
21 | Correct | 7 ms | 9724 KB | Output is correct |
22 | Correct | 7 ms | 9684 KB | Output is correct |
23 | Execution timed out | 1080 ms | 10252 KB | Time limit exceeded |
24 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 9684 KB | Output is correct |
2 | Correct | 6 ms | 9684 KB | Output is correct |
3 | Correct | 6 ms | 9684 KB | Output is correct |
4 | Correct | 5 ms | 9684 KB | Output is correct |
5 | Correct | 5 ms | 9684 KB | Output is correct |
6 | Correct | 5 ms | 9684 KB | Output is correct |
7 | Correct | 5 ms | 9708 KB | Output is correct |
8 | Correct | 6 ms | 9684 KB | Output is correct |
9 | Correct | 6 ms | 9712 KB | Output is correct |
10 | Correct | 7 ms | 9684 KB | Output is correct |
11 | Correct | 7 ms | 9684 KB | Output is correct |
12 | Correct | 7 ms | 9636 KB | Output is correct |
13 | Correct | 6 ms | 9684 KB | Output is correct |
14 | Correct | 6 ms | 9704 KB | Output is correct |
15 | Correct | 7 ms | 9684 KB | Output is correct |
16 | Correct | 9 ms | 9684 KB | Output is correct |
17 | Correct | 8 ms | 9684 KB | Output is correct |
18 | Correct | 7 ms | 9708 KB | Output is correct |
19 | Correct | 8 ms | 9684 KB | Output is correct |
20 | Correct | 9 ms | 9684 KB | Output is correct |
21 | Correct | 7 ms | 9724 KB | Output is correct |
22 | Correct | 7 ms | 9684 KB | Output is correct |
23 | Execution timed out | 1080 ms | 10252 KB | Time limit exceeded |
24 | Halted | 0 ms | 0 KB | - |