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
- #include "bits/stdc++.h"
-
- using namespace std;
-
- #define inf 12345678
-
- static const int maxn = 1e5 + 5;
-
- vector <int> graph[maxn];
- int IN[maxn], OUT[maxn], dp[maxn], degree[maxn], root;
-
- inline void dfs1(int u = 1, int p = -1)
- {
- IN[u] = inf;
- for (int v : graph[u])
- {
- if (v == p) continue;
- dfs1(v, u);
- IN[u] = min(IN[u], 1 + IN[v]);
- }
- if (degree[u] == 1 && u != 1) IN[u] = 0;
- }
-
- inline void dfs2(int u = 1, int p = -1)
- {
- int min1 = inf;
- int min2 = inf;
- for (int v : graph[u])
- {
- if (v == p) continue;
- if (IN[v] <= min1)
- {
- min2 = min1;
- min1 = IN[v];
- }
- else if (IN[v] < min2)
- {
- min2 = IN[v];
- }
- }
- for (int v : graph[u])
- {
- if (v == p) continue;
- int use = min1;
- if (IN[v] == use) use = min2;
- OUT[v] = min(1 + OUT[u], 2 + use);
- dfs2(v, u);
- }
- }
-
-
- int main(int argc, char const *argv[])
- {
-
- int tnode;
- scanf("%d", &tnode);
- for (int i = 1; i < tnode; i++)
- {
- int u, v;
- scanf("%d %d", &u, &v);
- degree[u]++;
- degree[v]++;
- graph[u].push_back(v);
- graph[v].push_back(u);
- }
- dfs1();
- memset(OUT, inf, sizeof OUT);
- if (degree[1] == 1) OUT[1] = 0;
- dfs2();
- for (int i = 1; i <= tnode; i++)
- {
- dp[i] = min(IN[i], OUT[i]);
- }
- sort(dp + 1, dp + tnode + 1);
- int sum_3PO = 0;
- int sum_Darth_Vade = 0;
- for (int i = 1; i <= tnode; i++)
- {
- if (i & 1) sum_3PO += dp[i];
- else sum_Darth_Vade += dp[i];
- }
- if (sum_3PO < sum_Darth_Vade) puts("3PO");
- else if (sum_3PO > sum_Darth_Vade) puts("Darth Vader");
- else puts("Draw");
- }
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.