oj.uz

Submission #884792

# Submission time Handle Problem Language Result Execution time Memory
884792 2023-12-08T12:23:16 Z HossamHero7 Parkovi (COCI22_parkovi) C++14
10 / 110
 90 ms 36436 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 2e5 + 5;
vector<pair<int,ll>> adj[N];
ll dp_down[N] , dp_up[N];
void dfs(int node,int par){
    for(auto [ch,c] :  adj[node]){
        if(ch == par) continue;
        dfs(ch,node);
        dp_down[node] = max(dp_down[node] , dp_down[ch]+c);
    }
}
void dfs2(int node,int par){
    pair<ll,ll> mx{0,0};
    for(auto [ch,c] :  adj[node]){
        if(ch == par) continue;
        if(mx.first < dp_down[ch] + c) {
            swap(mx.first,mx.second);
            mx.first = dp_down[ch] + c;
        }
        else if(mx.second < dp_down[ch] + c){
            mx.second = dp_down[ch] + c;
        }
    }
    for(auto [ch,c] : adj[node]){
        if(ch == par) continue;
        ll x = 0;
        if(mx.first == dp_down[ch] + c) x = mx.second;
        else x = mx.first;
        dp_up[ch] = max(dp_up[node] + c , x + c);
        dfs2(ch,node);
    }
}
void solve(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n-1;i++){
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    dfs(1,0);
    dfs2(1,0);
    pair<ll,int> ans = {1e18,0};
    for(int i=1;i<=n;i++) ans = min(ans , {max(dp_down[i] , dp_up[i]),i});
    cout<<ans.first<<endl<<ans.second<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:9:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
    9 |     for(auto [ch,c] :  adj[node]){
      |              ^
Main.cpp: In function 'void dfs2(int, int)':
Main.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto [ch,c] :  adj[node]){
      |              ^
Main.cpp:27:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for(auto [ch,c] : adj[node]){
      |              ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6232 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 31572 KB Output is correct
2 Correct 83 ms 36436 KB Output is correct
3 Correct 65 ms 21972 KB Output is correct
4 Correct 85 ms 21840 KB Output is correct
5 Correct 79 ms 21248 KB Output is correct
6 Correct 85 ms 21292 KB Output is correct
7 Correct 72 ms 20240 KB Output is correct
8 Correct 80 ms 20880 KB Output is correct
9 Correct 90 ms 21252 KB Output is correct
10 Correct 87 ms 21576 KB Output is correct
11 Correct 83 ms 23108 KB Output is correct
12 Correct 81 ms 23004 KB Output is correct
13 Correct 89 ms 24720 KB Output is correct
14 Correct 77 ms 21596 KB Output is correct
15 Correct 67 ms 21328 KB Output is correct
16 Correct 76 ms 22612 KB Output is correct
17 Correct 73 ms 21988 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 32776 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6232 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -