Advertisement
tien_noob

ATM - TLE (Impossible ??)

Jul 24th, 2021
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.57 KB | None | 0 0
  1. //Make CSP great again
  2. #include <bits/stdc++.h>
  3. #define TASK "TESTCODE"
  4. using namespace std;
  5. const int N = 5e5;
  6. int Low[N + 1], Num[N + 1], n, Component[N + 1], w[N + 1], Money[N + 1], m, s, p, Count = 0, componentcount = 0, res = 0, d[N + 1];
  7. vector<int> Adj[N + 1];
  8. bool Free[N + 1], Junction[N + 1];
  9. stack<int> Stack;
  10. void read()
  11. {
  12.     cin >> n >> m;
  13.     fill(Free + 1, Free + n + 1, true);
  14.     fill(Junction + 1, Junction + n + 1, false);
  15.     for(int i = 1; i <= m; ++ i)
  16.     {
  17.         int u, v;
  18.         cin >> u >> v;
  19.         Adj[u].push_back(v);
  20.     }
  21.     for (int i = 1; i <= n; ++ i)
  22.     {
  23.         cin >> w[i];
  24.     }
  25.     cin >> s >> p;
  26.     for (int i = 1; i <= p; ++ i)
  27.     {
  28.         int u;
  29.         cin >> u;
  30.         Junction[u] = true;
  31.     }
  32. }
  33. void Visit(int u)
  34. {
  35.     ++Count;
  36.     Low[u] = Num[u] = Count;
  37.     Stack.push(u);
  38.     for (int v : Adj[u])
  39.     {
  40.         if (Free[v])
  41.         {
  42.             if (Num[v] != 0)
  43.             {
  44.                 Low[u] = min(Low[u], Num[v]);
  45.             }
  46.             else
  47.             {
  48.                 Visit(v);
  49.                 Low[u] = min(Low[u], Low[v]);
  50.             }
  51.         }
  52.     }
  53.     if (Num[u] == Low[u])
  54.     {
  55.         vector<int> P;
  56.         ++componentcount;
  57.         int sum = 0;
  58.         int v;
  59.         do
  60.         {
  61.             v = Stack.top();
  62.             Stack.pop();
  63.             P.push_back(v);
  64.             sum += w[v];
  65.             Component[v] = componentcount;
  66.             Free[v] = false;
  67.         }
  68.         while (v != u);
  69.         for (int v : P)
  70.         {
  71.             Money[v] = sum;
  72.         }
  73.     }
  74. }
  75. void DFS(int u)
  76. {
  77.     if (Junction[u])
  78.     {
  79.         res = max(res, d[u]);
  80.     }
  81.     for (int v : Adj[u])
  82.     {
  83.         int add = 0;
  84.         if (Component[u] != Component[v])
  85.         {
  86.             add = Money[v];
  87.         }
  88.         if (d[u] + add > d[v])
  89.         {
  90.             d[v] = d[u] + add;
  91.             DFS(v);
  92.         }
  93.     }
  94. }
  95. void Debug()
  96. {
  97.     for (int i = 1; i <= n; ++ i)
  98.     {
  99.         cout << Component[i] << ' ';
  100.     }
  101. }
  102. void solve()
  103. {
  104.     for (int i = 1; i <= n; ++ i)
  105.     {
  106.         if (Num[i] == 0)
  107.         {
  108.             Visit(i);
  109.         }
  110.     }
  111.     d[s] = Money[s];
  112.     DFS(s);
  113.     cout << res;
  114. }
  115. int main()
  116. {
  117.     ios_base::sync_with_stdio(false);
  118.     cin.tie(nullptr);
  119.     //freopen(TASK".INP", "r", stdin);
  120.     //freopen(TASK".OUT", "w", stdout);
  121.     int t = 1;
  122.     bool typetest = false;
  123.     if (typetest)
  124.     {
  125.         cin >> t;
  126.     }
  127.     for (int __ = 1; __ <= t; ++ __)
  128.     {
  129.         read();
  130.         solve();
  131.     }
  132. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement