제출 #500598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500598		GenericAccount	Cheap flights (LMIO18_pigus_skrydziai)	C++17	100 / 100	565 ms	56732 KiB

pigus_skrydziai

#include <bits/stdc++.h>

using namespace std;

long long N, M;
// N-miestu skaicius, M-poru skaicius

struct Best {
  long long to;
  long long pelnas;
  Best() {
    this->to = -1;
    this->pelnas = -1;
  }
};

map<pair<long long, long long>, long long>pelnas;

void checkForBest(long long a, long long b, long long pelnas, vector<pair<Best, Best>> & pelningiausi) {
  if (pelnas > pelningiausi[a].first.pelnas) {
    pelningiausi[a].second = pelningiausi[a].first;
    pelningiausi[a].first.to = b;
    pelningiausi[a].first.pelnas = pelnas;
  }
  else if(pelnas>pelningiausi[a].second.pelnas){
     pelningiausi[a].second.to = b;
     pelningiausi[a].second.pelnas = pelnas;
  }
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  cin >> N >> M;
  vector<pair<Best, Best>> pelningiausi(N);
  vector<long long> visas_pelnas(N);
  long long a, b, p;
  for (long long i = 0; i < M; i++) {
    cin >> a >> b >> p;

    visas_pelnas[a - 1] += p;
    visas_pelnas[b - 1] += p;
    checkForBest(a - 1, b - 1, p, pelningiausi);
    checkForBest(b - 1, a - 1, p, pelningiausi);
    if (b > a)
      swap(a, b);
    pelnas[make_pair(a - 1, b - 1)] = p;
  }

  long long best = 0;
  for (long long peln : visas_pelnas) {
    best = max(best, peln);
  }

  for (int i = 0; i < pelningiausi.size(); i++) {
      b = min(pelningiausi[i].first.to, pelningiausi[i].second.to);
    if (b != -1) {
      a = max(pelningiausi[i].first.to, pelningiausi[i].second.to);
      long long tri=pelningiausi[i].first.pelnas + pelningiausi[i].second.pelnas + pelnas[make_pair(a, b)];
      best=max(best, tri);
    }
  }
  // for(pair<Best, Best> bp : pelningiausi){
  //   cout<<bp.first.to<<" "<<bp.first.pelnas<<endl;
  //   cout<<bp.second.to<<" "<<bp.second.pelnas<<endl;
  //   cout<<"--------------"<<endl;
  // }

  cout << best << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

pigus_skrydziai.cpp: In function 'int main()':
pigus_skrydziai.cpp:55:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<Best, Best> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for (int i = 0; i < pelningiausi.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~

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