Submission #884792

#	Time	Username	Problem	Language	Result	Execution time	Memory
884792		HossamHero7	Parkovi (COCI22_parkovi)	C++14	10 / 110	90 ms	36436 KiB

Main

#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 (stderr)

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
• Subtask 2: 10 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60