fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "000"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define el "\n"
  13. #define MASK(i) (1LL<<(i))
  14. #define BIT(i,j) (((i)>>(j))&1)
  15. #define TIME 1.0*clock()/CLOCKS_PER_SEC
  16. #define LOG 20
  17.  
  18. const int MAX=4e5+5;
  19. int n,m;
  20. vector<int> adj[MAX];
  21. ll val[MAX];
  22.  
  23. int compCount,compID[MAX];
  24. ll compSum[MAX];
  25. stack<int> st;
  26. int timer,low[MAX],num[MAX];
  27. bool inStack[MAX];
  28. void tarjan(int u)
  29. {
  30.     low[u]=num[u]=++timer;
  31.     st.push(u); inStack[u]=1;
  32.     for(int v:adj[u])
  33.     {
  34.         if(!num[v])
  35.         {
  36.             tarjan(v);
  37.             low[u]=min(low[u],low[v]);
  38.         }
  39.         else if(inStack[v])
  40.         {
  41.             low[u]=min(low[u],num[v]);
  42.         }
  43.     }
  44.     if(low[u]==num[u])
  45.     {
  46.         ++compCount;
  47.         while(true)
  48.         {
  49.             int v=st.top(); st.pop();
  50.             inStack[v]=0;
  51.             compID[v]=compCount;
  52.             compSum[compCount]+=val[v];
  53.             if(v==u) break;
  54.         }
  55.     }
  56. }
  57.  
  58. vector<int> adjTree[MAX];
  59. int in[MAX];
  60. ll f[MAX];
  61. vector<int> topo;
  62. void topoSort()
  63. {
  64.     topo.pb(0);
  65.     queue<int> q;
  66.     foru(i,1,compCount)
  67.     {
  68.         if(!in[i]) q.push(i);
  69.     }
  70.     while(!q.empty())
  71.     {
  72.         int u=q.front(); q.pop();
  73.         topo.pb(u);
  74.         for(int v:adjTree[u])
  75.         {
  76.             --in[v];
  77.             if(!in[v]) q.push(v);
  78.         }
  79.     }
  80. }
  81.  
  82. void calc()
  83. {
  84.     f[compID[1]]=compSum[compID[1]];
  85.     foru(i,1,compCount)
  86.     {
  87.         int u=topo[i];
  88.         if(f[u]!=0)
  89.         {
  90.             for(int v:adjTree[u])
  91.             {
  92. //                cerr<<v<<el;
  93. //                cerr<<f[v]<<' '<<compSum[v]<<el;
  94.                 f[v]=max(f[v],f[u]+compSum[v]);
  95.             }
  96.         }
  97.     }
  98.     cout<<f[compID[n]];
  99. }
  100.  
  101. int main()
  102. {
  103.     fastio
  104.     if(fopen(FILE ".inp","r"))
  105.     {
  106.         freopen(FILE ".inp","r",stdin); freopen(FILE ".out","w",stdout);
  107.     }
  108.     cin>>n>>m;
  109.     foru(i,1,n) cin>>val[i];
  110.     foru(i,1,m)
  111.     {
  112.         int u,v; cin>>u>>v;
  113.         adj[u].pb(v);
  114.     }
  115.     foru(i,1,n)
  116.     {
  117.         if(!num[i]) tarjan(i);
  118.     }
  119.  
  120.     foru(i,1,n)
  121.     {
  122.         int u=compID[i];
  123.         for(int x:adj[i])
  124.         {
  125.             int v=compID[x];
  126.             if(u!=v)
  127.             {
  128.                 adjTree[u].pb(v);
  129.                 in[v]++;
  130.             }
  131.         }
  132.     }
  133.     topoSort();
  134.     calc();
  135.  
  136.     return 0;
  137. }
  138.  
Success #stdin #stdout 0.01s 26152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wYvMzi
language:
C++14 (gcc 8.3)
created:
7 hours 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!