제출 #1139338

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139338		mariac	Cheap flights (LMIO18_pigus_skrydziai)	C++20	0 / 100	205 ms	327680 KiB

pigus_skrydziai

#include <bits/stdc++.h>

using namespace std;
const int NMAX = 3e5;
int n, m;
vector <pair<int,  long long>> graph[NMAX+1];
vector <int> sum(NMAX+1, 0), antecedent(NMAX+1, 0);
vector <vector<int>> mat;
int stea_max = 0;
bitset <NMAX+1> vis;
long long maxim(long long a, long long b)
{
    if(a>=b)
        return a;
    return b;
}
void read()
{
    int a, b, c;
    cin>>n>>m;
    mat.assign(n+1, vector<int>(n+1, 0));
    for(int i=1; i<=m; i++)
    {
        cin>>a>>b>>c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
        sum[a]+=c;
        sum[b]+=c;
        stea_max = maxim(stea_max, sum[a]);
        stea_max = maxim(stea_max, sum[b]);
        mat[a][b]=c;
        mat[b][a]=c;
    }
}
long long dfs(int node, int parent, int parent2)
{
    long long rez = 0;//lungimea maxima a unui ciclu din 3 muchii din aceasta componenta conexa
    vis[node] = 1;
    for(auto [next, price]:graph[node])
    {
        if(vis[next] == 1 && next!=parent)//am detectat ciclu >=2
        {
            if(parent2 == next)//ciclul are lunmgimea 3
            {
                rez  = maxim(rez, mat[next][node] + mat[node][parent] + mat[parent][next]);
            }
        }
        else
        {
            antecedent[next] = node;
            dfs(next, node, parent);
        }

    }
    return rez;
}
long long cicle3()
{
    long long rez;//lungimea maxima a unui ciclu din 3 muchii
    //for(int i=1; i<=n; i++) parent[i] = i;
    for(int i=1; i<=n; i++)
    {
        if(vis[i]==0)
            rez = max(rez, dfs(i, i, i));
    }
    return rez;
}
int main()
{
    read();
    cout<<stea_max;
    //cout<<maxim( stea_max, cicle3());
    return 0;
}
/*
oricare doua muchii trebuie sa aiba un nod in comun
apm
va fi ori stea ori triunghi
*/

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