Advertisement
Guest User

Untitled

a guest
Nov 19th, 2017
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.44 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <cstdio>
  5. #include <cmath>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. const int MAXN = 1000000;
  11.  
  12. vector<vector<int> > g(MAXN), gr(MAXN);
  13. vector<vector<int> > g_w(MAXN);
  14. vector<char> used(MAXN);
  15. vector<int> order;
  16. vector<long long> sum(MAXN);
  17. vector<int> comp_by_point(MAXN);
  18. vector<int> component[MAXN];
  19. long long dp[MAXN];
  20. vector<vector<int> > comp_graph(MAXN);
  21. vector<vector<int> > comp_graph_weight(MAXN);
  22. int n_component = 0;
  23.  
  24. void dfs1(int v) {
  25.     used[v] = true;
  26.     for (size_t i = 0; i<g[v].size(); ++i)
  27.         if (!used[g[v][i]])
  28.             dfs1(g[v][i]);
  29.     order.push_back(v);
  30. }
  31.  
  32. void dfs2(int v) {
  33.     used[v] = true;
  34.     component[n_component].push_back(v);
  35.     comp_by_point[v] = n_component;
  36.     for (size_t i = 0; i<gr[v].size(); ++i)
  37.         if (!used[gr[v][i]])
  38.             dfs2(gr[v][i]);
  39. }
  40.  
  41. long long dfs3(int v)
  42. {
  43.     long long ans = 0;
  44.     for (int i = 0; i < (int)comp_graph[v].size(); i++)
  45.     {
  46.         if (dp[comp_graph[v][i]] == -1)
  47.             dp[comp_graph[v][i]] = dfs3(comp_graph[v][i]);
  48.         ans = max(ans, dp[comp_graph[v][i]] + comp_graph_weight[v][i]);
  49.     }
  50.     return ans + sum[v];
  51. }
  52.  
  53. long long f(int x)
  54. {
  55.     /*int l = 0, r = 1e4 * 3;
  56.     while (r > l)
  57.     {
  58.         int m = (r + l + 1) / 2;
  59.         if (m * (m + 1) / 2 < x)
  60.             l = m;
  61.         else
  62.             r = m - 1;
  63.     }*/
  64.  
  65.     long long l = (int)((-1 + sqrt(1 + 8 * x)) / 2 + 0.00000001);
  66.  
  67.     return (l + 1)* x - (l * (l + 1) * (2 * l + 1) / 6 + l * (l + 1) / 2) / 2;
  68. }
  69.  
  70. int main()
  71. {
  72.     int n, m, s;
  73.     cin >> n >> m;
  74.     for (int i = 0; i < m; i++)
  75.     {
  76.         int a, b, w;
  77.         scanf("%d %d %d", &a, &b, &w);
  78.         a--; b--;
  79.         g[a].push_back(b);
  80.         g_w[a].push_back(w);
  81.         gr[b].push_back(a);
  82.     }
  83.     cin >> s;
  84.     s--;
  85.  
  86.     for (int i = 0; i < MAXN; i++)
  87.         used[i] = false;
  88.     for (int i = 0; i < n; ++i)
  89.         if (!used[i])
  90.             dfs1(i);
  91.  
  92.     for (int i = 0; i < MAXN; i++)
  93.         used[i] = false;
  94.     for (int i = 0; i < n; ++i) {
  95.         int v = order[n - 1 - i];
  96.         if (!used[v]) {
  97.             dfs2(v);
  98.             n_component++;
  99.         }
  100.     }
  101.  
  102.     for (int i = 0; i < n_component; i++)
  103.         dp[i] = -1;
  104.  
  105.     for (int i = 0; i < n; i++)
  106.     {
  107.         for (int j = 0; j < (int)g[i].size(); j++)
  108.         {
  109.             if (comp_by_point[i] == comp_by_point[g[i][j]])
  110.             {
  111.                 sum[comp_by_point[i]] += f(g_w[i][j]);
  112.             }
  113.             else
  114.             {
  115.                 comp_graph[comp_by_point[i]].push_back(comp_by_point[g[i][j]]);
  116.                 comp_graph_weight[comp_by_point[i]].push_back(g_w[i][j]);
  117.             }
  118.         }
  119.     }
  120.  
  121.     cout << dfs3(comp_by_point[s]) << endl;
  122.  
  123.  
  124.  
  125.     //system("pause");
  126.     return 0;
  127. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement