oj.uz

Submission #499107

# Submission time Handle Problem Language Result Execution time Memory
499107 2021-12-27T08:46:25 Z aurims Cheap flights (LMIO18_pigus_skrydziai) C++14
0 / 100
 385 ms 56512 KB 
#include <bits/stdc++.h>
#define debug cout << "alio\n"
#define pb push_back
#define ll long long
#define MAX (int)3e5
using namespace std;

vector<int> adj[MAX];
map<pair<int, int>, int> pe;

int main()
{
	int N, M;
	cin >> N >> M;
	for(int i = 0; i < M; i++)
	{
		int a, b;
		ll p;
		cin >> a >> b >> p;
		adj[a-1].pb(b-1);
		adj[b-1].pb(a-1);
		pe[{a, b}] = p;
		pe[{b, a}] = p;
	}
	ll mx = -1;
	for(int i = 0; i < N; i++)
	{
		if(adj[i].empty())
			continue;
		ll sum_tr = 0;
		ll sum_zv = 0;
		// perrenkam zvaigzdes
		for(int sidx : adj[i])
		{
			sum_zv += pe[{i, sidx}];
		}
		// perrenkam trikampius
		//cout << i << "-tojo miesto kaimynai:\n";
		for(int j = 0; j < adj[i].size()-1; j++) // gali pasirodyt, kad kils gresme jeigu yra tik du miestai, kuriuos jungia 1 briauna, bet td jie po zvaigzdute palenda ir juos vstk isrenka, net nereikia sito ciklo
		{
			int kaim1 = adj[i][j];
			int kaim2 = adj[i][j+1];
			/*
			cout << kaim1 << ' ' << miestai[i].pelnas[kaim1] << '\n';
			cout << kaim2 << ' ' << miestai[i].pelnas[kaim2] << '\n';
			cout << "Tarpusavy " << miestai[kaim1].pelnas[kaim2] << '\n';
			*/
			if(pe.find({kaim1, kaim2}) != pe.end()) // jeigu i-tojo miesto kaimynai j ir j+1 irgi turi kelia, tai susidaro trikampis
				sum_tr = pe[{kaim1, kaim2}] + pe[{i, kaim1}] + pe[{i, kaim2}];
			//cout << '\n';
		}
		if(sum_zv > mx) mx = sum_zv;
		if(sum_tr > mx) mx = sum_tr;
	}
	cout << mx << '\n';
}

Compilation message

pigus_skrydziai.cpp: In function 'int main()':
pigus_skrydziai.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int j = 0; j < adj[i].size()-1; j++) // gali pasirodyt, kad kils gresme jeigu yra tik du miestai, kuriuos jungia 1 briauna, bet td jie po zvaigzdute palenda ir juos vstk isrenka, net nereikia sito ciklo
      |                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 385 ms 56512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 385 ms 56512 KB Output isn't correct
2 Halted 0 ms 0 KB -