Submission #1272413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272413		huhuhuhuhu	Voting Cities (NOI22_votingcity)	C++20	30 / 100	380 ms	1188 KiB

Main

#include <bits/stdc++.h>
#include <cmath>

using namespace std;

long long n, e, k;
long long quest;
vector<pair<long long, long long>> rel[5005];
pair<long long, long long> par[5005];
long long dist[5005];
bool isTown[20005];

vector<long long> vote;
// vector<array<long long, 6>> q[5005];
// vector<array<long long, 6>*> res;

vector<array<long long, 6>> questions;
priority_queue<long long> pq;

void getdis(array<long long, 6> &arr, long long price) {
  stack<long long> st;
  for (int i = 0; i < 5; i++) {
    if (arr[i] == -1ll) {
      continue;
    }
    long long top = pq.top();
    pq.pop();
    st.push(top);
    price -= top;
    price += top * i / 10;
  }
  arr[5] = price;
  while (!st.empty()) {
    pq.push(st.top());
    st.pop();
  }
}

int main() {
  cin >> n >> e >> k;
  for (int i = 0; i <= n; i++) {
    dist[i] = INFINITY;
    par[i] = {-1, 2e12};
  }
  for (int i = 0; i < k; i++) {
    long long v;
    cin >> v;
    vote.push_back(v);
  }
  for (int i = 0; i < e; i++) {
    long long u, v, p;
    cin >> u >> v >> p;
    rel[v].push_back({u, p});
  }

  cin >> quest;
  for (int i = 0; i < quest; i++) {
    array<long long, 6> inp;
    for (int j = 0; j < 6; j++) {
      cin >> inp[j];
    }
    // q[pos].push_back(inp);
    // res.push_back(&q[pos][q[pos].size() - 1]);
    questions.push_back(inp);
  }

  priority_queue<array<long long, 4>> que;
  for (auto &x : vote) {
    isTown[x] = true;
    que.push({0, x, -1, 0});
  }
  while (!que.empty()) {
    auto top = que.top();
    que.pop();

    if (top[0] >= dist[top[1]]) {
      continue;
    }
    par[top[1]] = {top[2], top[3]};
    dist[top[1]] = top[0];
    for (int i = 0; i < rel[top[1]].size(); i++) {
      auto next = rel[top[1]][i];
      que.push({top[0] + next.second, next.first, top[1], next.second});
    } 
  }

  for (int i = 0; i < questions.size(); i++) {
    auto cur = questions[i];
    long long pos = cur[0];
    long long total = 0;
    priority_queue<long long> price;
    bool onTown = false;
    while (pos != -1) {
      if (isTown[pos]) {
        onTown = true;
      }
      total += par[pos].second;
      price.push(par[pos].second);
      pos = par[pos].first;
      // cout << pos << endl;
    }
    if (!onTown) {
      cout << -1 << endl;
      continue;
    }
    for (long long i = 5; i >= 1; i--) {
      if (cur[i] == -1) {
        continue;
      }
      if (price.empty()) {
        break;
      }
      long long top = price.top();
      long long newPrice = cur[i] + (top * (10ll - i)) / 10ll;
      // cout << i << " " << min(newPrice, top) << endl;
      if (newPrice >= top) {
        continue;
      }
      price.pop();
      total = total - top + newPrice;
    }
    cout << total << endl;
  }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:42:15: warning: overflow in conversion from 'float' to 'long long int' changes value from '+Inff' to '9223372036854775807' [-Woverflow]
   42 |     dist[i] = INFINITY;
      |               ^~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 0 / 5
• Subtask 6: 10 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 50