Submission #1220740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220740		sleepntsheep	Cheap flights (LMIO18_pigus_skrydziai)	C++17	28 / 100	364 ms	86020 KiB

pigus_skrydziai

#include <cstdio>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>

#define N 300050

using namespace std;

int tc, m,n, a[N], b[N], c[N]
	;
long long suma[N * 2];

map<int,int>x[N];
vector<pair<int, int> > g[N * 2];

long long get(int u,int v){
	return x[u][v];
}

int main() {
	tc=1;
	while (tc--) {
		scanf("%d%d", &n,&m);
		for (int i = 0; i < m; ++i) {
			scanf("%d%d%d", a + i, b + i, c + i);
			suma[a[i]] += c[i], suma[b[i]] += c[i];
			x[a[i]][b[i]]=max(x[a[i]][b[i]],c[i]);
			x[b[i]][a[i]]=max(x[b[i]][a[i]],c[i]);
			g[a[i]].emplace_back(-c[i], b[i]),
				g[b[i]].emplace_back(-c[i], a[i]);
		}
		for(int i=1;i<=n;++i){
			sort(g[i].begin(),g[i].end());
			if(g[i].size()>2)
				g[i].resize(2);
		}

		long long answer = 0;
		for (int i = 1; i <= n; ++i)
			answer = max(answer, suma[i]);

		for (int i=1;i<=n;++i){
			if(g[i].size()<2)continue;
			int u=g[i][0].second,v=g[i][1].second;
			answer=max(answer,0ll-g[i][0].first-g[i][1].first+get(u,v));
		}

		printf("%lld\n", answer);
	}
	return 0;
}

Compilation message (stderr)

pigus_skrydziai.cpp: In function 'int main()':
pigus_skrydziai.cpp:25:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |                 scanf("%d%d", &n,&m);
      |                 ~~~~~^~~~~~~~~~~~~~~
pigus_skrydziai.cpp:27:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |                         scanf("%d%d%d", a + i, b + i, c + i);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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