fork download 
  1. /*
  2. * Author     : Apu Das Orgho
  3.  * Problem   : The Monster's Dice (Medium Version)
  4.  * Created on: 27-09-2025
  5.  */
  6. #include<bits/stdc++.h>
  7. #define iamspeed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  8. #define endl '\n'
  9. #define ll int
  10. using namespace std;
  11. const int N = 5e6 + 5;
  12. const ll mod = 998244353;
  13. string s, ss;
  14. ll d, x, y, z, cnt, t, tt, cnt2, sum, ans, res, q, n, m, k, i, j;
  15. vector<pair<ll,ll> > graph[N];
  16. vector<ll> cst(N);
  17. ll dijk(int sz, int src) {
  18.     priority_queue<pair<ll,ll> > pq;
  19.     pq.push({0, src});
  20.     vector<bool> vis(sz + 2, 0);
  21.     while (!pq.empty()) {
  22.         auto [cost,node] = pq.top();
  23.         pq.pop();
  24.         cost *= -1;
  25.         if (vis[node])continue;
  26.         cst[node] = cost;
  27.         vis[node] = true;
  28.         for (auto [child,wt]: graph[node]) {
  29.             pq.push({-cost - wt, child});
  30.         }
  31.     }
  32.     return -1;
  33. }
  34.  
  35. int main() {
  36.     iamspeed
  37.     ///freopen("input.txt","r",stdin);
  38.     ///freopen("output.txt","w",stdout);
  39.     cin >> n >> m >> q;
  40.     set<ll> st;
  41.     int id = 1;
  42.     map<ll,ll> mp, mp2;
  43.     map<ll, bool> block;
  44.     vector<pair<ll,ll> > pr;
  45.     st.insert(1);
  46.     st.insert(n);
  47.     while (m--) {
  48.         cin >> x >> y >> z;
  49.         st.insert(x);
  50.         st.insert(y);
  51.         pr.push_back({x, y});
  52.     }
  53.     vector<ll> queries(q);
  54.     for (i = 0; i < q; i++) {
  55.         cin >> queries[i];
  56.         st.insert(queries[i]);
  57.     }
  58.     vector<ll> v2;
  59.     copy(st.begin(), st.end(), back_inserter(v2));
  60.     st.clear();
  61.     vector<pair<ll,ll> > v;
  62.     for (ll x: v2) {
  63.         for (i = 0; i <= 6; i++) {
  64.             if (!st.count(x + i) && x + i <= n) {
  65.                 st.insert(x + i);
  66.                 mp[x + i] = id++;
  67.             }
  68.         }
  69.     }
  70.     ll sz = id;
  71.     sort(v.begin(), v.end());
  72.     cst.assign(id + 5, -1);
  73.     for (i = 0; i <= id + 5; i++) {
  74.         graph[i].clear();
  75.     }
  76.     for (auto [xx,yy]: pr) {
  77.         xx = mp[xx], yy = mp[yy];
  78.         block[xx] = true;
  79.         ///graph[xx].push_back({yy, 0});
  80.     }
  81.     for (auto [val,id]: mp) {
  82.         v.push_back({val, id});
  83.     }
  84.     for (i = 0; i < v.size(); i++) {
  85.         auto [ai,id] = v[i];
  86.         if (block.count(id))continue;
  87.         int ct = 0;
  88.         for (j = i + 1; j < v.size(); j++) {
  89.             auto [aj,nid] = v[j];
  90.             ll dist = (aj - ai) / 6 + ((aj - ai) % 6 != 0);
  91.             graph[nid].push_back({id, dist});
  92.             if (aj == v[j - 1].first + 1)ct++;
  93.             else ct = 1;
  94.             if (ct >= 6)break;
  95.         }
  96.     }
  97.     for (auto [xx,yy]: pr) {
  98.         xx = mp[xx], yy = mp[yy];
  99.         graph[yy].push_back({xx, 0});
  100.     }
  101.     dijk(sz, mp[n]);
  102.     for (int id = 0; id < queries.size(); id++) {
  103.         cout << cst[mp[queries[id]]] << endl;
  104.     }
  105.  
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0.04s 140044KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/3tZYQu
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!