Advertisement
YEZAELP

o64_feb_c2_emer

Jan 30th, 2022
699
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "emergency.h"
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5. const int inf = 1e9;
  6. const int MXN = 2e5 + 5;
  7. using pi = pair <int, int>;
  8. vector <pi> g[MXN];
  9. bool isA[MXN], isB[MXN];
  10. int ans, sub[MXN], node[MXN];
  11.  
  12. void dfs1(int u, int p){
  13.     if(isA[u]) sub[u] = 0;
  14.     for(auto vw: g[u]){
  15.         int v = vw.first, w = vw.second;
  16.         if(v == p) continue;
  17.         dfs1(v, u);
  18.         if(sub[v] != -inf) sub[u] = max(sub[u], sub[v] + w);
  19.     }
  20. }
  21.  
  22. void dfs2(int u, int p){
  23.  
  24.     if(isA[u]) node[u] = max(node[u], 0);
  25.     if(isB[u]) ans = max({ans, sub[u], node[u]});
  26.  
  27.     int mx1 = -inf, mx2 = -inf, idx = 0;
  28.     for(auto vw: g[u]){
  29.         int v = vw.first, w = vw.second;
  30.         if(v == p) continue;
  31.         int cur = sub[v] + w;
  32.         if(cur > mx1){
  33.             mx2 = mx1;
  34.             mx1 = cur;
  35.             idx = v;
  36.         }
  37.         else if(cur > mx2) mx2 = cur;
  38.  
  39.         if(node[u] != -inf) node[v] = node[u] + w;
  40.     }
  41.  
  42.     for(auto vw: g[u]){
  43.         int v = vw.first, w = vw.second;
  44.         if(v == p) continue;
  45.         if(v == idx) node[v] = max(node[v], mx2 + w);
  46.         else node[v] = max(node[v], mx1 + w);
  47.         dfs2(v, u);
  48.     }
  49. }
  50.  
  51. int furthest(int N, int nA, int nB, int roads[][2], int w[], int A[], int B[]){
  52.  
  53.     for(int i=0;i<N-1;i++){
  54.         int u = roads[i][0] + 1, v = roads[i][1] + 1;
  55.         g[u].push_back({v, w[i]});
  56.         g[v].push_back({u, w[i]});
  57.     }
  58.  
  59.     for(int i=0;i<nA;i++)
  60.         isA[ A[i] + 1] = true;
  61.  
  62.     for(int i=0;i<nB;i++)
  63.         isB[ B[i] + 1] = true;
  64.  
  65.     for(int u=1;u<=N;u++) sub[u] = node[u] = -inf;
  66.  
  67.     dfs1(1, -1), dfs2(1, -1);
  68.  
  69.     return ans;
  70. }
Advertisement
RAW Paste Data Copied
Advertisement