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(hateThemself[i])
  47.         {
  48.             sta[i] = 2;
  49.             continue;
  50.         }
  51.         if(hateThemself[hate[i]])
  52.             continue;
  53.         adj[i].push_back(hate[i]);
  54.         adj[hate[i]].push_back(i);
  55.     }
  56.     for(int i = 1; i <= n; i++)
  57.     {
  58.         sort(adj[i].begin(), adj[i].end());
  59.         auto it = unique(adj[i].begin(), adj[i].end());
  60.         adj[i].erase(it, adj[i].end());
  61.     }
  62. }
  63.  
  64. bool dfsForLoop(int u, int p)
  65. {
  66.     if(adj[u].size() <= 1)
  67.         curLineStart = u;
  68.     sta[u] = 1;
  69.     for(int v: adj[u])
  70.     {
  71.         if(v == p) continue;
  72.         if(sta[v] == 0)
  73.         {
  74.             pre[v] = u;
  75.             if(dfsForLoop(v, u))
  76.                 return true;
  77.         }
  78.         else if(sta[v] == 1)
  79.         {
  80.             curStart = v;
  81.             curEnd = u;
  82.             return true;
  83.         }
  84.     }
  85.     sta[u] = 2;
  86.     return false;
  87. }
  88.  
  89. void dfsVal(int u, int p)
  90. {
  91.     dp[u][1] = 0;
  92.     dp[u][0] = 0;
  93.     for(int v: adj[u])
  94.     {
  95.         if(v == p || vis[v]) continue;
  96.         dfsVal(v, u);
  97.         dp[u][1] += dp[v][0];
  98.         dp[u][0] += max(dp[v][0], dp[v][1]);
  99.     }
  100.     dp[u][1] += val[u];
  101. }
  102.  
  103. vector<long long> newArray(vector<long long>curArr)
  104. {
  105.     long long base = 0;
  106.     vector<long long>ans;
  107.     for(int i = 0; i < curArr.size(); i++)
  108.         vis[curArr[i]] = true;
  109.     for(int i = 0; i < curArr.size(); i++)
  110.         dfsVal(curArr[i], -1);
  111.     for(int i = 0; i < curArr.size(); i++)
  112.     {
  113.         ans.push_back(dp[curArr[i]][1] - dp[curArr[i]][0]);
  114.         base += dp[curArr[i]][0];
  115.     }
  116.     ans.push_back(base);
  117.  
  118.     for(int i = 0; i < curArr.size(); i++)
  119.         vis[curArr[i]] = false;
  120.  
  121.     return ans;
  122. }
  123.  
  124. long long solveNoCycle()
  125. {
  126.     dfsVal(curLineStart, -1);
  127.     return max(dp[curLineStart][0], dp[curLineStart][1]);
  128. }
  129.  
  130. long long solveCycle()
  131. {
  132.     vector<long long>cycle;
  133.     cycle.push_back(curStart);
  134.     int count = 0;
  135.     for(int v = curEnd; v != curStart; v = pre[v])
  136.     {
  137.         cycle.push_back(v);
  138.         count++;
  139.         if(count > n) break; // prevent infinite loop
  140.     }
  141.     cycle = newArray(cycle);
  142.     long long base = cycle.back();
  143.     cycle.pop_back();
  144.     long long maxAns = -oo;
  145.     long long maxVal1 = 0, maxVal2 = 0;
  146.     for(int i = 1; i < cycle.size(); i++)
  147.     {
  148.         long long cur = max(maxVal1, maxVal2+cycle[i]);
  149.         maxVal2 = maxVal1;
  150.         maxVal1 = cur;
  151.     }
  152.     maxAns = max(maxAns, maxVal1);
  153.     maxVal1 = 0;
  154.     maxVal2 = 0;
  155.     for(int i = 0; i < cycle.size()-1; i++)
  156.     {
  157.         long long cur = max(maxVal1, maxVal2+cycle[i]);
  158.         maxVal2 = maxVal1;
  159.         maxVal1 = cur;
  160.     }
  161.     maxAns = max(maxAns, maxVal1);
  162.     return maxAns+base;
  163. }
  164.  
  165. long long solveFor(int u)
  166. {
  167.     if(!dfsForLoop(u, -1))
  168.     {
  169.         return solveNoCycle();
  170.     }
  171.     return solveCycle();
  172. }
  173.  
  174. long long solve()
  175. {
  176.     long long ans = 0;
  177.     for(int i = 1; i <= n; i++)
  178.     {
  179.         if(hateThemself[i])
  180.             continue;
  181.         if(sta[i] == 0)
  182.             ans += solveFor(i);
  183.     }
  184.     return ans;
  185. }
  186.  
  187. int main()
  188. {
  189.     ios_base::sync_with_stdio(0);
  190.     cin.tie(0);
  191.     int t;
  192.     cin >> t;
  193.     while(t--)
  194.     {
  195.         readData();
  196.         cout << solve() << "\n";
  197.     }
  198.     return 0;
  199. }
  200.  
Success #stdin #stdout 0.01s 8368KB
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/QrfjRH
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!