Submission #1220738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220738		sleepntsheep	Cheap flights (LMIO18_pigus_skrydziai)	C++17	53 / 100	140 ms	50868 KiB

pigus_skrydziai

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

#define N 700050

using namespace std;

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

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

long long get(int u,int v){
	for(auto[_,w]:g[u])if(w==v)return -_;
	return 0;
}

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];
			g[a[i]].emplace_back(-c[i], b[i]),
				g[b[i]].emplace_back(-c[i], a[i]);
		}
		for(int i=1;i<=2*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 <= 2 * n; ++i)
			answer = max(answer, suma[i]);

		for (int i=1;i<=2*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);

		for (int i=0;i<=2*n;++i)suma[i]=0, g[i].clear();
	}
	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: 25 / 25
• Subtask 3: 16 / 16
• Subtask 4: 0 / 47