Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <sstream>
- #include <limits>
- // Assume no invalid operation
- void FindMaximumPath(std::vector<std::vector<long long int>> &directed_graph, std::vector< long long int> &parent,
- std::vector<long long int> &value,
- long long int &max_value, long long int &root_res, long long int current, long long int previous)
- {
- // The idea is that for each node, we find 2 paths
- // (the paths from that node to any depth and yields the maximum path)
- // In other words, these 2 paths for each node are the maximum path and the second maximum path.
- // the maximum among all the nodes are the maximum path of the tree
- long long int first_max_path = 0;
- long long int second_max_path = 0;
- for (auto child : directed_graph[current]) {
- FindMaximumPath(directed_graph, parent, value, max_value, root_res, child, current);
- if (first_max_path <= value[child]) {
- second_max_path = first_max_path;
- first_max_path = value[child];
- } else {
- if (second_max_path <= value[child]) {
- second_max_path = value[child];
- }
- }
- }
- if (max_value <= first_max_path + second_max_path + value[current]) {
- max_value = first_max_path + second_max_path + value[current];
- root_res = current;
- }
- value[current] += first_max_path; // we need to store the maximum path so far into the nodes that we have visited
- }
- void print_test_graph(std::vector<std::vector<long long int>> &v) {
- int i = 0;
- for (auto x : v) {
- std::cout << i << ' ';
- for (auto y : x) {
- // print pair
- std::cout << y << " ";
- }
- ++i;
- std::cout << '\n';
- }
- }
- void print_test(std::vector<long long int> &v) {
- int i = 0;
- for (int i = 0; i < v.size(); ++i) {
- std::cout << i << ", " << v[i] << '\n';
- }
- }
- int main() {
- int n, op;
- // pair of {dest, distance}
- std::cin >> n >> op;
- // no clue why n + op + 1 does not work as size
- std::vector<std::vector<long long int>> directed_graph(20005);
- // this vector stores the value of each node_i and later on, the maximum path at node_i
- std::vector<long long int> value(20005);
- std::vector<long long int> parent(20005);
- std::fill(parent.begin(), parent.end(), -1);
- long long int src, dest, d;
- std::cin >> src >> d;
- long long int root = src;
- value[src] = d;
- parent[src] = -1; // we denotes no parents aka root also as -1
- for (int i = 0; i < n; ++i) {
- std::cin >> src >> dest >> d;
- directed_graph[src].push_back(dest);
- value[dest] = d;
- parent[dest] = src;
- }
- std::cin.ignore(); // to ignore newline
- for(int m = 0; m < op; ++m) {
- std::string buf;
- std::getline(std::cin, buf);
- std::istringstream iss(buf);
- std::string s;
- std::getline(iss, s, ' ');
- // wonky stuff here Add will break if the directed_graph are suddenly disjointed
- if (s[0] == 'A') {
- std::getline(iss, s, ' ');
- int add_src = std::stoi(s);
- std::getline(iss, s, ' ');
- int add_dest = std::stoi(s);
- std::getline(iss, s, ' ');
- int add_d = std::stoi(s);
- directed_graph[add_src].push_back(add_dest);
- value[add_dest] = add_d;
- parent[add_dest] = add_src;
- } else if (buf[0] == 'C') {
- long long int max_value = std::numeric_limits<long long int>::min();
- long long int root_result = root;
- std::vector<long long int> prev_value = value; // copy the old value so it does not get deleted after runnign the algo
- FindMaximumPath(directed_graph, parent, value, max_value, root_result, root, -1);
- std::cout << "Maximum Value: " << max_value << '\n';
- std::cout << "Root of the Path: " << root_result << '\n';
- value = prev_value;
- } else {
- // Delete
- std::getline(iss, s, ' ');
- long long int node = std::stoi(s);
- long long int par = parent[node];
- if (node > 20005) {
- continue;
- }
- // This is a bit wonky as we did not delete parent -> child connection
- // but we deleted child -> parent connection
- for (auto child : directed_graph[node]) {
- directed_graph[par].push_back(child); // transfer children of node to parent
- parent[child] = par; // set parent of child as par
- }
- directed_graph[node].clear(); // delete current node's children
- // set parent to -1
- parent[node] = -1;
- // get 9/10 without setting it into negative
- value[node] = std::numeric_limits<long long int>::min(); // actually very important as a placeholder so this won't get count (it might break)
- // THIS IS A WORKAROUND as especially if we delete leaves, we technically do not delete leave,
- // we only set the leaf as 0 weight but DFS can still go
- // First sol : Set a really small number so the path does not every count (more than -100000 (the limit))
- // Second sol : Reiterate the parent node then delete the connection by maybe copying back and forth to the array (more legit solution)
- }
- iss.str("");
- }
- long long int max_value = std::numeric_limits<long long int>::min();
- long long int root_result = root;
- FindMaximumPath(directed_graph, parent, value, max_value, root_result, root, -1);
- std::cout << "Final Root: " << root_result << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement