oj.uz

Submission #624983

# Submission time Handle Problem Language Result Execution time Memory
624983 2022-08-09T08:39:19 Z MilosMilutinovic Ceste (COCI17_ceste) C++14
160 / 160
 956 ms 24396 KB 
/**
 *    author:  wxhtzdy
 *    created: 09.08.2022 10:15:44
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> m;
  vector<vector<array<int, 3>>> g(n);
  for (int i = 0; i < m; i++) {
    int x, y, t, c;
    cin >> x >> y >> t >> c;
    --x; --y;
    g[x].push_back({y, t, c});
    g[y].push_back({x, t, c}); 
  }
  vector<set<pair<int, int>>> dist(n);
  dist[0].insert({0, 0});
  set<array<int, 3>> st;
  st.insert({0, 0, 0}); 
  auto Update = [&](int v, int t, int c) {
    auto it = dist[v].lower_bound({t, c});    
    while (it != dist[v].end()) {
      if (it->first >= t && it->second >= c) {
        if (st.find({v, it->first, it->second}) != st.end()) {
          st.erase(st.find({v, it->first, it->second}));
        }
        it = dist[v].erase(it);
      } else {
        break;
      }
    }
    it = dist[v].lower_bound({t, c});             
    if (it != dist[v].begin()) {
      it = prev(it);           
      if (it->first < t && it->second > c) {
        dist[v].emplace(t, c);
        st.insert({t, c, v});
      }
    } else {
      dist[v].emplace(t, c);
      st.insert({t, c, v});
    }
  };
  while (!st.empty()) {
    auto it = st.begin();
    int t = (*it)[0];
    int c = (*it)[1]; 
    int u = (*it)[2];
    st.erase(it);
    for (auto& p : g[u]) {
      Update(p[0], t + p[1], c + p[2]);
    }
  }
  for (int i = 1; i < n; i++) {
    if (dist[i].empty()) {
      cout << -1 << '\n';
    } else {
      long long ans = 1e18;
      for (auto& p : dist[i]) {
        ans = min(ans, p.first * 1LL * p.second);
      }
      cout << ans << '\n';
    }
  }                         
  return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 3 ms 556 KB Output is correct
3 Correct 3 ms 468 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1464 KB Output is correct
2 Correct 49 ms 1492 KB Output is correct
3 Correct 39 ms 800 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 19096 KB Output is correct
2 Correct 746 ms 8376 KB Output is correct
3 Correct 4 ms 740 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 4580 KB Output is correct
2 Correct 758 ms 16900 KB Output is correct
3 Correct 15 ms 1492 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 17348 KB Output is correct
2 Correct 741 ms 22448 KB Output is correct
3 Correct 666 ms 19724 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 21320 KB Output is correct
2 Correct 607 ms 19004 KB Output is correct
3 Correct 956 ms 24396 KB Output is correct