Saturday, January 26, 2019

[toph.co] Darth Vader and 3PO on a Tree!

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Darth Vader and 3PO on a Tree! 
Source            : toph.co
Category          : Graph Theory, Dynamic Programing
Algorithm         : DP on Tree, In Out DP
Verdict           : Accepted


  1. #include "bits/stdc++.h"  
  2.   
  3. using namespace std;  
  4.   
  5. #define inf                                   12345678  
  6.   
  7. static const int maxn = 1e5 + 5;  
  8.   
  9. vector <int> graph[maxn];  
  10. int IN[maxn], OUT[maxn], dp[maxn], degree[maxn], root;  
  11.   
  12. inline void dfs1(int u = 1, int p = -1)  
  13. {  
  14.       IN[u] = inf;  
  15.       for (int v : graph[u])  
  16.       {  
  17.             if (v == p) continue;  
  18.             dfs1(v, u);  
  19.             IN[u] = min(IN[u], 1 + IN[v]);  
  20.       }  
  21.       if (degree[u] == 1 && u != 1) IN[u] = 0;  
  22. }  
  23.   
  24. inline void dfs2(int u = 1, int p = -1)  
  25. {  
  26.       int min1 = inf;  
  27.       int min2 = inf;  
  28.       for (int v : graph[u])  
  29.       {  
  30.             if (v == p) continue;  
  31.             if (IN[v] <= min1)  
  32.             {  
  33.                   min2 = min1;  
  34.                   min1 = IN[v];  
  35.             }  
  36.             else if (IN[v] < min2)  
  37.             {  
  38.                   min2 = IN[v];  
  39.             }  
  40.       }  
  41.       for (int v : graph[u])  
  42.       {  
  43.             if (v == p) continue;  
  44.             int use = min1;  
  45.             if (IN[v] == use) use = min2;  
  46.             OUT[v] = min(1 + OUT[u], 2 + use);  
  47.             dfs2(v, u);  
  48.       }  
  49. }  
  50.   
  51.   
  52. int main(int argc, char const *argv[])  
  53. {  
  54.       //freopen("in.txt", "r", stdin);  
  55.       int tnode;  
  56.       scanf("%d", &tnode);  
  57.       for (int i = 1; i < tnode; i++)  
  58.       {  
  59.             int u, v;  
  60.             scanf("%d %d", &u, &v);  
  61.             degree[u]++;  
  62.             degree[v]++;  
  63.             graph[u].push_back(v);  
  64.             graph[v].push_back(u);  
  65.       }  
  66.       dfs1();  
  67.       memset(OUT, inf, sizeof OUT);  
  68.       if (degree[1] == 1) OUT[1] = 0;  
  69.       dfs2();  
  70.       for (int i = 1; i <= tnode; i++)  
  71.       {  
  72.             dp[i] = min(IN[i], OUT[i]);  
  73.       }  
  74.       sort(dp + 1, dp + tnode + 1);  
  75.       int sum_3PO = 0;  
  76.       int sum_Darth_Vade = 0;  
  77.       for (int i = 1; i <= tnode; i++)  
  78.       {  
  79.             if (i & 1) sum_3PO += dp[i];  
  80.             else sum_Darth_Vade += dp[i];  
  81.       }  
  82.       if (sum_3PO < sum_Darth_Vade) puts("3PO");  
  83.       else if (sum_3PO > sum_Darth_Vade) puts("Darth Vader");  
  84.       else puts("Draw");  
  85. }  

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.