Submission #550171

#	Time	Username	Problem	Language	Result	Execution time	Memory
550171		fadi57	Cheap flights (LMIO18_pigus_skrydziai)	C++14	100 / 100	1447 ms	106184 KiB

pigus_skrydziai

#include<bits/stdc++.h>
using namespace std;

const int mx=500009;
typedef long long ll;
map<pair<int,int>,ll>mp;
vector<pair<int,ll>>adj[mx];
int n,m;
ll ans;
int vis[mx];
void dfs(int node,int par){
 vis[node]=2;
   for(auto it:adj[node]){
        if(it.first==par){continue;}
       if(vis[it.first]==2&&mp.find({par,it.first})!=mp.end()){
          ans=max(ans,1LL*(it.second+mp[{it.first,par}]+mp[{node,par}]));
       }else if(vis[it.first]){
         continue;
       }else{
         dfs(it.first,node);

       }


    }

  vis[node]=1;


}
int main()
{
     ios_base::sync_with_stdio(0);
     cin.tie();
    cin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
     adj[x].push_back({y,w});
       adj[y].push_back({x,w});
       mp[{x,y}]=w;
       mp[{y,x}]=w;
    }

    for(int i=1;i<=n;i++){
          if(!vis[i]){
            dfs(i,0);
          }
          ll tmp=0;
          for(auto it:adj[i]){
            tmp+=it.second;
          }
          ans=max(ans,tmp);
    }
    cout<<ans;

}

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