fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. #define maxN 100007
  9. #define oo 1000000000000000000
  10.  
  11. vector<int>adj[maxN];
  12. long long val[maxN];
  13. bool vis[maxN] = {false};
  14. int sta[maxN] = {0};
  15. int pre[maxN] = {0};
  16. int hate[maxN] = {0};
  17. bool hateThemself[maxN] = {false};
  18. int n;
  19. int curStart, curEnd;
  20. int curLineStart;
  21. long long dp[maxN][2] = {0};
  22.  
  23. void readData()
  24. {
  25.     int v;
  26.     cin >> n;
  27.     for(int i = 1; i <= n; i++)
  28.     {
  29.         sta[i] = 0;
  30.         adj[i].clear();
  31.         pre[i] = 0;
  32.         vis[i] = false;
  33.         hateThemself[i] = false;
  34.         dp[i][0] = 0;
  35.         dp[i][1] = 0;
  36.     }
  37.     for(int i = 1; i <= n; i++)
  38.     {
  39.         cin >> val[i];
  40.         cin >> hate[i];
  41.         if(i == hate[i])
  42.             hateThemself[i] = true;
  43.     }
  44.     for(int i = 1; i <= n; i++)
  45.     {
  46.         if(hate[i] == -1)
  47.             continue;
  48.         if(hateThemself[i])
  49.         {
  50.             sta[i] = 2;
  51.             continue;
  52.         }
  53.         if(hateThemself[hate[i]])
  54.             continue;
  55.         adj[i].push_back(hate[i]);
  56.         adj[hate[i]].push_back(i);
  57.     }
  58.     for(int i = 1; i <= n; i++)
  59.     {
  60.         sort(adj[i].begin(), adj[i].end());
  61.         auto it = unique(adj[i].begin(), adj[i].end());
  62.         adj[i].erase(it, adj[i].end());
  63.     }
  64. }
  65.  
  66. bool dfsForLoop(int u, int p)
  67. {
  68.     if(adj[u].size() <= 1)
  69.         curLineStart = u;
  70.     sta[u] = 1;
  71.     for(int v: adj[u])
  72.     {
  73.         if(v == p) continue;
  74.         if(sta[v] == 0)
  75.         {
  76.             pre[v] = u;
  77.             if(dfsForLoop(v, u))
  78.                 return true;
  79.         }
  80.         else if(sta[v] == 1)
  81.         {
  82.             curStart = v;
  83.             curEnd = u;
  84.             return true;
  85.         }
  86.     }
  87.     sta[u] = 2;
  88.     return false;
  89. }
  90.  
  91. void dfsVal(int u, int p)
  92. {
  93.     dp[u][1] = 0;
  94.     dp[u][0] = 0;
  95.     for(int v: adj[u])
  96.     {
  97.         if(v == p || vis[v]) continue;
  98.         dfsVal(v, u);
  99.         dp[u][1] += dp[v][0];
  100.         dp[u][0] += max(dp[v][0], dp[v][1]);
  101.     }
  102.     dp[u][1] += val[u];
  103. }
  104.  
  105. vector<long long> newArray(vector<long long>curArr)
  106. {
  107.     long long base = 0;
  108.     vector<long long>ans;
  109.     for(int i = 0; i < curArr.size(); i++)
  110.         vis[curArr[i]] = true;
  111.     for(int i = 0; i < curArr.size(); i++)
  112.         dfsVal(curArr[i], -1);
  113.     for(int i = 0; i < curArr.size(); i++)
  114.     {
  115.         ans.push_back(dp[curArr[i]][1] - dp[curArr[i]][0]);
  116.         base += dp[curArr[i]][0];
  117.     }
  118.     ans.push_back(base);
  119.  
  120.     for(int i = 0; i < curArr.size(); i++)
  121.         vis[curArr[i]] = false;
  122.  
  123.     return ans;
  124. }
  125.  
  126. long long solveNoCycle()
  127. {
  128.     dfsVal(curLineStart, -1);
  129.     return max(dp[curLineStart][0], dp[curLineStart][1]);
  130. }
  131.  
  132. long long solveCycle()
  133. {
  134.     vector<long long>cycle;
  135.     cycle.push_back(curStart);
  136.     int count = 0;
  137.     for(int v = curEnd; v != curStart; v = pre[v])
  138.     {
  139.         cycle.push_back(v);
  140.         count++;
  141.         if(count > n) break; // prevent infinite loop
  142.     }
  143.     cycle = newArray(cycle);
  144.     long long base = cycle.back();
  145.     cycle.pop_back();
  146.     long long maxAns = -oo;
  147.     long long maxVal1 = 0, maxVal2 = 0;
  148.     for(int i = 1; i < cycle.size(); i++)
  149.     {
  150.         long long cur = max(maxVal1, maxVal2+cycle[i]);
  151.         maxVal2 = maxVal1;
  152.         maxVal1 = cur;
  153.     }
  154.     maxAns = max(maxAns, maxVal1);
  155.     maxVal1 = 0;
  156.     maxVal2 = 0;
  157.     for(int i = 0; i < cycle.size()-1; i++)
  158.     {
  159.         long long cur = max(maxVal1, maxVal2+cycle[i]);
  160.         maxVal2 = maxVal1;
  161.         maxVal1 = cur;
  162.     }
  163.     maxAns = max(maxAns, maxVal1);
  164.     return maxAns+base;
  165. }
  166.  
  167. long long solveFor(int u)
  168. {
  169.     if(!dfsForLoop(u, -1))
  170.     {
  171.         return solveNoCycle();
  172.     }
  173.     return solveCycle();
  174. }
  175.  
  176. long long solve()
  177. {
  178.     long long ans = 0;
  179.     for(int i = 1; i <= n; i++)
  180.     {
  181.         if(hateThemself[i])
  182.             continue;
  183.         if(sta[i] == 0)
  184.             ans += solveFor(i);
  185.     }
  186.     return ans;
  187. }
  188.  
  189. int main()
  190. {
  191.     ios_base::sync_with_stdio(0);
  192.     cin.tie(0);
  193.     int t;
  194.     cin >> t;
  195.     while(t--)
  196.     {
  197.         readData();
  198.         cout << solve() << "\n";
  199.     }
  200.     return 0;
  201. }
  202.  
Success #stdin #stdout 0.01s 8848KB
comments (?)
stdin
copy 
4
3
3 2
5 1
1 2
3
3 2
2 3
2 1
4
1 3
2 3
3 4
4 2
4
2 2
3 1
4 4
3 3
stdout
copy 
5
3
5
7
https://ideone.com/1UlQSP
language:
C++14 (gcc 8.3)
created:
8 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!