fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // start policy based data structures
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7.  
  8. using namespace __gnu_pbds;
  9.  
  10. template <class T>
  11. using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  12. // end policy based data structures
  13.  
  14. // start debugging helpers
  15. #ifdef LOCAL
  16. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  17. #else
  18. #define trace(...) 42
  19. #endif
  20. template <typename Arg1>
  21. void __f(const char *name, Arg1 &&arg1) {
  22.     cerr << name << ": " << arg1 << endl;
  23. }
  24. template <typename Arg1, typename... Args>
  25. void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  26.     const char *comma = strchr(names + 1, ',');
  27.     cerr.write(names, comma - names) << ": " << arg1 << "\t|";
  28.     __f(comma + 1, args...);
  29. }
  30.  
  31. #define print(x)           \
  32.     for (auto it : x)      \
  33.         cout << it << ' '; \
  34.     cout << '\n';
  35. // end debugging helpers
  36.  
  37. #define all(x) x.begin(), x.end()
  38. #define mem1(a) memset(a, -1, sizeof(a))
  39. #define mem0(a) memset(a, 0, sizeof(a))
  40. #define int long long
  41.  
  42. // typedef long long ll;
  43. typedef unsigned long long ull;
  44. const int N = 505;
  45. int times[N];
  46. int in[N];
  47. vector<int> adj[N];
  48.  
  49. int do_magic(int node, int priority) {
  50.     // calculate indegree
  51.     mem0(in);
  52.     for (int i = 0; i < N; i++)
  53.         for (auto kid : adj[i])
  54.             in[kid]++;
  55.  
  56.     // add all nodes with indegree 0 to the queue
  57.     priority_queue<pair<int, int>> q;
  58.     for (int i = 0; i < N; i++) {
  59.         if (in[i] > 0) continue;
  60.         if (i == node) q.push({priority, i});
  61.         else q.push({0, i});
  62.     }
  63.  
  64.     // process queue
  65.     int total_time = 0;
  66.     while (!q.empty()) {
  67.         auto top = q.top();
  68.         q.pop();
  69.         int cur_node = top.second;
  70.         if (cur_node == node) {
  71.             return total_time;
  72.         }
  73.         total_time += times[cur_node];
  74.         // relax edges
  75.         for (auto kid : adj[cur_node]) {
  76.             in[kid]--;
  77.             if (!in[kid]) {
  78.                 if (kid == node) q.push({priority, kid});
  79.                 else q.push({0, kid});
  80.             }
  81.  
  82.         }
  83.     }    
  84.     return total_time;
  85. }
  86.  
  87. void solve(int V, int E, int case_num) {
  88.     //reset
  89.     mem0(times);
  90.     for (auto v : adj) v.clear();
  91.  
  92.     for (int i = 1; i <= V; i++) cin >> times[i];
  93.     for (int i = 0; i < E; i++) {
  94.         int x, y;
  95.         cin >> x >> y;
  96.         adj[x].push_back(y);
  97.     }
  98.     int Q;
  99.     cin >> Q;
  100.     vector<int> queries(Q);
  101.     for (int i = 0; i < Q; i++) {
  102.         cin >> queries[i];
  103.     }
  104.     cout << "Case #" << case_num << ":\n";
  105.     for (int i = 0; i < Q; i++) {        
  106.         int mini = do_magic(queries[i], INT_MAX);
  107.         int maxi = do_magic(queries[i], INT_MIN);
  108.         cout << (maxi - mini) << '\n';
  109.     }
  110.     cout << '\n';
  111. }
  112.  
  113. signed main() {
  114.     ios::sync_with_stdio(false);
  115.     cin.tie(0);
  116.     int t = 1;
  117.     // cin >> t;
  118.     // while (t--) solve();
  119.     int V, E, case_num = 1;
  120.     while (cin >> V >> E) {
  121.         if (!V) break;
  122.         solve(V, E, case_num);
  123.         case_num++;
  124.     }
  125.     return 0;
  126. }
Success #stdin #stdout 0s 4924KB
comments (?)
stdin
copy 
4 4
4 3 2 1
2 1
2 4
3 1
3 4
2
1 2

4 4
4 3 2 1
2 1
2 4
3 1
3 4
2
3 4

0 0
stdout
copy 
Case #1:
1
2

Case #2:
3
4
https://ideone.com/VPbOmf
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!