CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:mooc.fi~486604
Submission time:2021-10-04 19:47:59 +0300
Language:C++11
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.01 s1, 2, 3details
#20.75 s2, 3details
#30.24 s3details

Code

#include <bits/stdc++.h>

using namespace std; 
int N;
vector<pair<int,int>> v[200000];
int sum; 
stack<int> S; 

void haku(int r, int e, int weight){
    int k=weight; 
    if(!S.empty()){
      k =min(weight, S.top());}
    sum+=k; 
    if(k==weight&&k!=0){
        S.push(k);
    }
    
    for(auto u: v[r]){
        if(u.first!=e) haku(u.first, r, u.second);
    }
    if(!S.empty()) S.pop(); 

}


   
int main()
{
    int i,a,b,c;
    sum=0; 
    cin>>N; 
    
    for(i=0; i<N-1; i++){
        cin>>a>>b>>c;
        v[a].push_back({b,c});
        v[b].push_back({a, c});
    }
    for(i=1;i<=N;i++){
        while(!S.empty()) S.pop();
        
        haku(i, 0, 0);
       
    }
    cout<<sum/2;
    return 0;
}

Test details

Test 1

Group: 1, 2, 3

Verdict:

input
100
1 2 74
1 3 100
2 4 50
3 5 40
...

correct output
88687

user output
169129

Test 2

Group: 2, 3

Verdict:

input
5000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1103702320243776

user output
-763056289

Test 3

Group: 3

Verdict:

input
200000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1080549209850010931

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc