oj.uz

Submission #498725

# Submission time Handle Problem Language Result Execution time Memory
498725 2021-12-26T09:11:09 Z Kipras Cheap flights (LMIO18_pigus_skrydziai) C++14
0 / 100
 339 ms 58580 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

const ll maxN = (1e5*5)+10;

ll n, m;
vector<pair<ll, ll>> adj[maxN];
vector<pair<ll, ll>> adjFast[maxN];

ll findVal(ll v, ll v1){
    ll l = 0, h = adjFast[v1].size()-1;
    while(l<h){
        ll mid = l+((h-l)/2);
        if(adjFast[v1][mid].first==v)return adjFast[v1][mid].second;
        else if(adjFast[v1][mid].first<v)l=mid+1;
        else h=mid-1;
    }
    return -1;
}

int main()
{

    ios_base::sync_with_stdio(0);cin.tie(nullptr);

    cin>>n>>m;
    for(ll i = 0; i < m; i++){
        ll a, b, c;
        cin>>a>>b>>c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
        adjFast[a].push_back({b, c});
        adjFast[b].push_back({a, c});
    }

    for(ll i = 1; i <= n; i++)sort(adjFast[i].begin(), adjFast[i].end());

    ll ans=0;

    for(ll i = 1; i <= n; i++){
        ll temp=0;
        for(auto x : adj[i]){
            temp+=x.second;
        }
        for(ll x = 0; x < (ll)(adj[i].size())-1; x++){
            ll val=-1;
            ll v1=adj[i][x].first, v2=adj[i][x+1].first;
            val = findVal(v2, v1);
            if(val==-1)continue;
            temp+=adj[i][x].second+adj[i][x+1].second+val;
            ans=max(ans, temp);
            temp-=adj[i][x].second+adj[i][x+1].second+val;
        }

        ans=max(ans, temp);
    }

    cout<<ans;

    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 23776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 23776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 44740 KB Output is correct
2 Correct 339 ms 58580 KB Output is correct
3 Incorrect 110 ms 35236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 44740 KB Output is correct
2 Correct 339 ms 58580 KB Output is correct
3 Incorrect 110 ms 35236 KB Output isn't correct
4 Halted 0 ms 0 KB -