fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long int ll;
  6. typedef unsigned long long int ull;
  7. typedef long double ld;
  8. typedef pair <ll, ll> pll;
  9. typedef pair <int, int> pii;
  10.  
  11. #define pb push_back
  12. #define mp make_pair
  13. #define ff first
  14. #define ss second
  15. #define all(a) a.begin(), a.end()
  16. #define sz(a) (ll)(a.size())
  17. #define endl "\n"
  18.  
  19. ll gcd(ll a, ll b)
  20. {
  21.     if(b==0)
  22.     {
  23.         return a;
  24.     }
  25.  
  26.     return gcd(b, a%b);
  27. }
  28.  
  29. const ll L = 505;
  30.  
  31. vector <ll> t(L);
  32. vector <ll> f[L];
  33. vector <ll> s[L];
  34. bool visited[L];
  35.  
  36. int main()
  37. {
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(NULL); cout.tie(NULL);
  40.  
  41.     ll tc = 0;
  42.  
  43.     while(true)
  44.     {
  45.         tc++;
  46.  
  47.         ll v, e;
  48.         cin >> v >> e;
  49.  
  50.         ll tot = 0;
  51.  
  52.         if(!v && !e)
  53.         {
  54.             break;
  55.         }
  56.  
  57.         for(ll i=0; i<L; i++)
  58.         {
  59.             f[i].clear();
  60.             s[i].clear();
  61.             t[i] = 0;
  62.         }
  63.  
  64.  
  65.         for(ll i=1; i<=v; i++)
  66.         {
  67.             cin >> t[i];
  68.  
  69.             tot+=t[i];
  70.         }
  71.  
  72.         for(ll i=0; i<e; i++)
  73.         {
  74.             ll a, b;
  75.             cin >> a >> b;
  76.  
  77.             f[a].pb(b);
  78.             s[b].pb(a);
  79.         }
  80.  
  81.         ll q;
  82.         cin >> q;
  83.  
  84.         cout << "Case #" << tc << ":" << endl;
  85.  
  86.         while(q--)
  87.         {
  88.             ll x;
  89.             cin >> x;
  90.  
  91.             queue <ll> q1, q2;
  92.  
  93.             for(ll i=0; i<L; i++)
  94.             {
  95.                 visited[i] = false;
  96.             }
  97.  
  98.             q1.push(x);
  99.             q2.push(x);
  100.  
  101.             ll sum1 = 0, sum2 = 0;
  102.  
  103.             while(!q1.empty())
  104.             {
  105.                 ll top = q1.front();
  106.                 q1.pop();
  107.  
  108.                 sum1+=t[top];
  109.  
  110.                 visited[top] = true;
  111.  
  112.                 for(auto i: f[top])
  113.                 {
  114.                     if(!visited[i])
  115.                     {
  116.                         q1.push(i);
  117.                     }
  118.                 }
  119.             }
  120.  
  121.             while(!q2.empty())
  122.             {
  123.                 ll top = q2.front();
  124.                 q2.pop();
  125.  
  126.                 sum2+=t[top];
  127.  
  128.                 visited[top] = true;
  129.  
  130.                 for(auto i: s[top])
  131.                 {
  132.                     if(!visited[i])
  133.                     {
  134.                         q2.push(i);
  135.                     }
  136.                 }
  137.             }
  138.  
  139.             cout << tot - sum1 - sum2 + t[x] << endl;
  140.         }
  141.  
  142.         cout << endl;
  143.     }
  144.  
  145.     return 0;
  146. }
Success #stdin #stdout 0s 15264KB
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/ljuSH7
language:
C++ (gcc 8.3)
created:
5 years 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!