Submission #1122597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122597		ardadut	Cheap flights (LMIO18_pigus_skrydziai)	C++20	0 / 100	326 ms	44004 KiB

pigus_skrydziai

#include <bits/stdc++.h>
    
#define ll long long
#define pb push_back
#define endl "\n"
#define vec vector<ll>
#define vecvec vector<vector<ll>>
    
using namespace std;
    
/*#define FileName ""
string Ghhhh = ".in";
string Ghhhhh = ".out";
ifstream Girdi(FileName + Ghhhh);
ofstream Cikti(FileName + Ghhhhh);
#define cin Girdi
#define cout Cikti*/

#define maxn 300005

ll n,m,ans = 0;
vector<ll> profit;
vector<vector<pair<ll,ll>>> adj;
vector<bool> vis;
map<pair<ll,ll>,ll> mapp;

inline void dfs(ll node, ll parent, ll edge){

    vis[node] = 1;

    for(auto go : adj[node]){
        ll a = go.first;
        ll b = parent;
        if(a > b) swap(a,b);
        if(mapp[{a,b}] > 0){
            ans = max(ans,go.second + edge + mapp[{a,b}]);
        }
        if(!vis[go.first]) dfs(go.first,node,go.second);
    }

}

inline void solve(){

    cin >> n >> m;
    adj.resize(n+1);
    vis.resize(n+1,0);
    profit.resize(n+1,0);

    while(m--){
        ll a,b,c;
        cin >> a >> b >> c;
        if(a > b) swap(a,b);
        profit[a] += c;
        profit[b] += c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
        mapp[{a,b}] = c;
    }

    dfs(1,-1,0);

    for(ll i = 1 ; i <= n ; i++){
        ans = max(ans,profit[i]);
    }

    cout << ans << endl;

}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    
}

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