oj.uz

Submission #316161

# Submission time Handle Problem Language Result Execution time Memory
316161 2020-10-25T15:53:13 Z laoriu Beads and wires (APIO14_beads) C++14
0 / 100
 4 ms 4992 KB 
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
using ll = long long ;
//#define int long long

using ii = pair < int , int > ;
const int MAX = 2e5+4,mod=1e9+7;
const int inf=0x3f3f3f3f;
int n,m;
vector < ii > pr[MAX];
void minn(int &a , int b){
if(b<a) a=b;
}
void maxx(int &a , int b){
if(b>a) a=b;
}
int dp[2][MAX];
void DFS(int v,int trc){
    int temp=0;
    for(ii u:pr[v])if(u.X!=trc){
        DFS(u.X,v);
        temp+=max(dp[1][u.X]+u.Y,dp[0][u.X]);
    }
    dp[1][v]=-inf;
    dp[0][v]=temp;
    for(ii u:pr[v])if(u.X!=trc){
        int x=dp[0][u.X]+u.Y- max(dp[1][u.X]+u.Y,dp[0][u.X]);
        maxx(dp[0][v],dp[1][v]+x+temp);
        maxx(dp[1][v],x );
    }
    dp[1][v]+=temp;
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("beads.inp", "r", stdin);//freopen("beads.out", "w", stdout);
    cin>>n;
    for(int i=1,x,y,c;i<n;i++){
        cin>>x>>y>>c;
        pr[x].pb(ii(y,c));
        pr[y].pb(ii(x,c));
    }
    DFS(1,0);
    cout<<dp[0][1];

}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Incorrect 4 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Incorrect 4 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Incorrect 4 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Incorrect 4 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -