fork download
copy 
  1. /*
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC target("avx,avx2,fma")
  4. */
  5. #include "bits/stdc++.h"
  6. using namespace std;
  7. #define ll long long
  8. #define Ft first
  9. #define Sd second
  10.  
  11. const int mx = 500;
  12.  
  13. int jobs, dpnd;
  14. int times[mx+1] = {0};
  15. vector<int> adj[mx+1];
  16. bool vis[mx+1] = {0};
  17.  
  18. void BFS(const int node, int& res, const int original){
  19.     res = 0;
  20.     if (vis[node]) return;
  21.  
  22.     vis[node] = true;
  23.  
  24.     vector<int> v;
  25.  
  26.     queue<int> q;
  27.     q.push(node);
  28.  
  29.     res += times[node];
  30.  
  31.     while (!q.empty()){
  32.         auto s = q.front();   q.pop();
  33.         v.push_back(s); 
  34.  
  35.         for (auto u : adj[s]){
  36.             if (u == original) {
  37.                 res = 0;
  38.                 for (auto it : v)
  39.                     vis[it] = 0;
  40.                 return;
  41.             }
  42.             if (vis[u]) continue;
  43.  
  44.             vis[u] = true;
  45.             v.push_back(u);
  46.             res += times[u];
  47.             q.push(u);
  48.         }
  49.     }
  50. }
  51.  
  52. void solve(void){
  53.     for (int i=1; i <= jobs; i++)
  54.         cin >> times[i];  
  55.  
  56.     while (dpnd-- > 0){
  57.         int j1,j2; cin >> j1 >> j2;
  58.         adj[j1].push_back(j2);
  59.     }  
  60.  
  61.     int Q; cin >> Q;
  62.     while (Q-- > 0){
  63.         memset(vis, 0, sizeof(vis));
  64.         int x; cin >> x;
  65.         int Mn = 0;
  66.         BFS(x, Mn, x);
  67.         if (Mn > 0)
  68.             Mn -= times[x];
  69.  
  70.         memset(vis, 0, sizeof(vis));
  71.  
  72.         int Mx = 0, total = 0;
  73.  
  74.         for (int i=1; i <= jobs; i++){
  75.             if (i == x) continue;
  76.  
  77.             BFS(i, total, x);
  78.             Mx += total;
  79.         }
  80.  
  81.         cout << Mx-Mn << '\n';
  82.     }    
  83. }
  84.  
  85. int main(void){
  86.      ios::sync_with_stdio(0); cin.tie(0);
  87. #ifndef ONLINE_JUDGE
  88.     freopen("output.txt", "w", stdout);
  89. #endif   
  90.     int Case = 1;
  91.  
  92.     while ((cin >> jobs >> dpnd) && jobs) {
  93.         cout << "Case #" << Case++ << ":\n";
  94.  
  95.         for (int i=1; i <= jobs; i++)
  96.             adj[i].clear();
  97.  
  98.         memset(times, 0, sizeof(times));
  99.         memset(vis, 0, sizeof(vis));
  100.  
  101.         solve();
  102.  
  103.         cout << "\n";
  104.     }
  105.  
  106. #ifndef ONLINE_JUDGE
  107.     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  108. #endif
  109.     return 0;
  110. }
Success #stdin #stdout 0.01s 5596KB
comments (?)
stdin
copy 
5 7
2 87 23 51 27
2 5
1 4
1 3
1 2
2 4
1 5
2 3
5
1 2 3 4 5

0 0
stdout
copy 
Case #1:
0
0
78
50
74
https://ideone.com/K3wPPD
UVA 10461 Difference
language:
C++14 (gcc 8.3)
created:
2 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!