oj.uz

Submission #550166

# Submission time Handle Problem Language Result Execution time Memory
550166 2022-04-17T12:48:50 Z fadi57 Cheap flights (LMIO18_pigus_skrydziai) C++14
0 / 100
 149 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;

const int mx=5009;
typedef long long ll;
map<pair<int,int>,int>mp;
vector<pair<int,int>>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]==1){
         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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Runtime error 149 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Runtime error 149 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -