Submission #1139393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139393		ansedra	Cheap flights (LMIO18_pigus_skrydziai)	C++20	53 / 100	354 ms	122552 KiB

pigus_skrydziai

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

const int Nmax = 300005;
typedef long long LL;

struct nod{
    LL cost_individual;
    int adancime;
    vector<int> vecini;
};

int n, m;
LL sol;
nod retea[Nmax];
unordered_map<int, LL> muchii[Nmax];

void citire(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int nod1, nod2;
    LL cost;

    cin >> n >> m;

    for(int i = 1; i <= m; i++){
        cin >> nod1 >> nod2 >> cost;

        muchii[nod1][nod2] = cost;
        muchii[nod2][nod1] = cost;

        retea[nod1].cost_individual += cost;
        retea[nod2].cost_individual += cost;

        retea[nod1].vecini.push_back(nod2);
        retea[nod2].vecini.push_back(nod1);
    }
}

void verificare_noduri_individuale(){
    sol = 0;
    for(int i = 1; i <= n; i++){
        sol = max(sol, retea[i].cost_individual);
    }
}

void dfs(int nod, int prev){
    for(int vecin : retea[nod].vecini){
        if(!retea[vecin].adancime){
            retea[vecin].adancime = retea[nod].adancime + 1;
            dfs(vecin, nod);
        }
    }

    for(int vecin : retea[nod].vecini){
        if(retea[vecin].adancime + 2 == retea[nod].adancime){
            if(muchii[vecin][prev] && muchii[prev][nod] && muchii[nod][vecin]){
                sol = max(sol, muchii[vecin][prev] + muchii[prev][nod] + muchii[nod][vecin]);
            }

            if(muchii[prev][vecin] && muchii[vecin][nod] && muchii[nod][prev]){
                sol = max(sol, muchii[prev][vecin] + muchii[vecin][nod] + muchii[nod][prev]);
            }
        }
    }
}

void procesare_cicluri(){
    for(int i = 1; i <= n; i++){
        if(!retea[i].adancime){
            retea[i].adancime = 1;
            dfs(i, 0);
        }
    }
}

void afisare_solutie(){
    cout << sol;
}

int main(){
    citire();
    verificare_noduri_individuale();
    procesare_cicluri();
    afisare_solutie();

    return 0;
}

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