Submission #1130162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130162		ttamx	Cheap flights (LMIO18_pigus_skrydziai)	C++20	53 / 100	211 ms	50760 KiB

pigus_skrydziai

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n);
    vector<ll> a(n);
    for(int i=0;i<m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        u--,v--;
        a[u]+=w,a[v]+=w;
        adj[u].emplace_back(v,w);
        adj[v].emplace_back(u,w);
    }
    ll ans=*max_element(a.begin(),a.end());
    vector<int> dep(n);
    vector<ll> dist(n);
    function<void(int,int)> dfs=[&](int u,int p){
        for(auto [v,w]:adj[u]){
            if(!dep[v]){
                dep[v]=dep[u]+1;
                dist[v]=dist[u]+w;
                dfs(v,u);
            }else if(dep[u]-dep[v]==2){
                ans=max(ans,dist[u]-dist[v]+w);
            }
        }
    };
    for(int i=0;i<n;i++){
        if(!dep[i]){
            dep[i]=1;
            dfs(i,-1);
        }
    }
    cout << ans;
}

• Subtask 1: 12 / 12
• Subtask 2: 25 / 25
• Subtask 3: 16 / 16
• Subtask 4: 0 / 47