Submission #795929

#	Time	Username	Problem	Language	Result	Execution time	Memory
795929		vjudge1	Cheap flights (LMIO18_pigus_skrydziai)	C++17	100 / 100	676 ms	77840 KiB

pigus_skrydziai

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int, int>

const int maxN = 1e6 + 10;

vector<pii> v[maxN], v1[maxN];
long long cnt[maxN], cnt1[maxN];
int n, m;

int main() {

    cin >> n >> m;
	

    for (int i = 1; i<=m; i++) {
    	int x, y, z;
    	scanf("%d%d%d", &x, &y, &z);
    	cnt[x]+=z;
    	cnt[y]+=z;
    	v[x].pb(mp(y, z));
    	v[y].pb(mp(x, z));
    }


    long long ans = 0;

    for (int i = 1; i<=n; i++) {
    	ans = max(ans, cnt[i]);
    }


    for (int i = 1; i<= n; i++) {
    	for (auto j: v[i]) {
    		if (j.first > i) continue;
    		int x = i;
    		int y = j.first;
    		int z = j.second;
    		if (v[x].size() > v[y].size()) swap(x, y);
    		v1[x].pb(mp(y, z));
    	}
    }

    for (int i = 1; i<=n; i++) {
    	for (auto j: v1[i]) {

    		for (auto k: v1[i]) {
    			cnt1[k.first] = k.second;
    		}

    		for (auto k: v1[j.first]) {
    			cnt1[k.first]+=k.second;
    			ans = max(ans, j.second + cnt1[k.first]);
    			cnt1[k.first] = 0;
    		}

    		for (auto k: v1[i]) {
    			cnt1[k.first] = 0;
    		}

    	}
    }

    cout << ans << endl;

	return 0;
}

Compilation message (stderr)

pigus_skrydziai.cpp: In function 'int main()':
pigus_skrydziai.cpp:26:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |      scanf("%d%d%d", &x, &y, &z);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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