제출 #1139367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139367		ansedra	Cheap flights (LMIO18_pigus_skrydziai)	C++20	53 / 100	402 ms	122548 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, int> 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);
        }
        else if(retea[vecin].adancime + 2 == retea[nod].adancime){
            sol = max(sol, 1LL * muchii[vecin][prev] + muchii[prev][nod] + muchii[nod][vecin]);
            sol = max(sol, 1LL * 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