fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define fi first
  5. #define se second
  6. #define siz(x) (int)(x.size())
  7. #define all(x) x.begin(), x.end()
  8. #define debug_arr(x,len) for(int _=1; _<=len; _++) cout<<x[_]<<" "; cout<<'\n';
  9. #define debug(x) cout<<'\n'<<#x<<": "<<x<<'\n';
  10. const int maxN = 1e6+5;
  11.  
  12. int n, m, start, vst[maxN], f[maxN], scc_id[maxN], val[maxN], dem = 0, dp[maxN];
  13. vector<pair<int,int>>adj[maxN], rev_adj[maxN];
  14. set<pair<int,int>>compress[maxN];
  15. vector<int>ord;
  16.  
  17. void prep()
  18. {
  19.     for(int i=1; i<=1e6; i+=1)
  20.     {
  21.         int xet = i*(i+1) / 2;
  22.         f[i]=f[i-1]+xet;
  23.     }
  24. }
  25.  
  26. int cal(int x)
  27. {
  28.     int tmp = sqrt(8*x + 1);
  29.     int res = (tmp - 1) / 2;
  30.     return res;
  31. }
  32. // n*(n+1) / 2 = x -> n*n + n = 2x 
  33. // -> 4n*n + 4n = 8x -> 8x + 1 = (2n+1)*(2n+1)
  34. // ->sqrt(8x+1) = (2n+1)
  35.  
  36. void dfs1(int u)
  37. {
  38.     vst[u] = 1;
  39.     for(auto i: adj[u])
  40.     {
  41.         if(!vst[i.fi]) dfs1(i.fi);
  42.     }
  43.     ord.push_back(u);
  44. }
  45.  
  46. void dfs2(int u)
  47. {
  48.     vst[u] = 1;
  49.     scc_id[u] = dem;
  50.     for(auto i: rev_adj[u])
  51.     {
  52.         if(!vst[i.fi]) dfs2(i.fi);
  53.     }
  54. }
  55.  
  56. void dfs3(int u, int v)
  57. {
  58.     vst[u] = 1;
  59.     for(auto i: compress[u])
  60.     {
  61.         if(i.fi == v) continue;
  62.         if(!vst[i.fi]) dfs3(i.fi, u);
  63.         dp[u] = max(dp[u], val[u] + dp[i.fi] + i.se);
  64.     }
  65. }
  66. void solve()
  67. {
  68.     for(int i=1; i<=n; i+=1)
  69.     {
  70.         if(!vst[i]) dfs1(i);
  71.     }
  72.     reverse(all(ord));
  73.     for(int i=1; i<=n; i+=1) vst[i] = 0;
  74.     for(auto i: ord)
  75.     {
  76.         if(!vst[i])
  77.         {
  78.             dem++; dfs2(i);
  79.         }
  80.     }
  81.     for(int i=1; i<=n; i+=1)
  82.     {
  83.         for(auto [j, w]: adj[i])
  84.         {
  85.             if(scc_id[j] == scc_id[i])
  86.             {
  87.                 val[scc_id[i]] += w * (cal(w) + 1) - f[cal(w)];
  88.             }
  89.             else compress[scc_id[i]].insert({scc_id[j], w});
  90.         }
  91.     }
  92.     for(int i=1; i<=dem; i+=1) dp[i] = val[i];
  93.     for(int i=1; i<=n; i+=1) vst[i] = 0;
  94.     for(int i=1; i<=dem; i+=1) 
  95.     {
  96.         if(!vst[i]) dfs3(i, 0);
  97.     }
  98.     cout<<dp[start]<<'\n';
  99. }
  100.  
  101. // dp[i] la so cach lay max nam neu bat dau tu dinh i
  102. int32_t main()
  103. {
  104.     ios_base::sync_with_stdio(0); cin.tie(0);
  105.     prep();
  106.     cin>>n>>m;
  107.     for(int i=1; i<=m; i+=1)
  108.     {
  109.         int x,y,w; cin>>x>>y>>w;
  110.         adj[x].push_back({y,w});
  111.         rev_adj[y].push_back({x,w});
  112.     }
  113.     cin>>start;
  114.     solve();
  115. }
Success #stdin #stdout 0.03s 106008KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/0HyFta
language:
C++14 (gcc 8.3)
created:
14 days 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!