fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. typedef long long ll;
  7. typedef long double ld;
  8. typedef pair<int, int> pii;
  9. typedef pair<ll, ll> pll;
  10. typedef vector<int> vi;
  11. typedef vector<ll> vll;
  12. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  13. #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
  14. #define pb push_back
  15. #define ff first
  16. #define ss second
  17.  
  18. const int N = 2e5 + 1;
  19. const ll INF = 4000000000000000000LL;
  20.  
  21. vector<pll> graf[N], odl[N];
  22. vi zb;
  23. ll dyst[N];
  24. int podd[N], odw[N];
  25.  
  26. struct oba{
  27.     ll v1, k1, v2, k2;
  28. };
  29.  
  30. vector<oba> pref[N], suf[N];
  31.  
  32. void poddrzewa(int v, int ojc){
  33.     podd[v] = 1;
  34.     for(pll x : graf[v]){
  35.         int u = x.ff;
  36.         if(odw[u] || u == ojc) continue;
  37.         poddrzewa(u, v);
  38.         podd[v] += podd[u];
  39.     }
  40. }
  41.  
  42. int znajdz(int v, int ojc, int r){
  43.     for(pll x : graf[v]){
  44.         int u = x.ff;
  45.         if(odw[u] || u == ojc) continue;
  46.         if(podd[u] > r / 2) return znajdz(u, v, r);
  47.     }
  48.     return v;
  49. }
  50.  
  51. void dfs_policz(int v, int ojc){
  52.     zb.pb(v);
  53.     for(pll x : graf[v]){
  54.         int u = x.ff;
  55.         if(u == ojc || odw[u]) continue;
  56.         dyst[u] = dyst[v] + x.ss;
  57.         dfs_policz(u, v);
  58.     }
  59. }
  60.  
  61. void decompose(int v){
  62.     poddrzewa(v, 0);
  63.     int c = znajdz(v, 0, podd[v]);
  64.     odw[c] = 1; dyst[c] = 0;
  65.     odl[c].pb({0, c});
  66.  
  67.     for(pll x : graf[c]){
  68.         int u = x.ff; ll w = x.ss;
  69.         if(odw[u]) continue;
  70.         dyst[u] = w;
  71.         zb.clear();
  72.         dfs_policz(u, 0);
  73.  
  74.         for(int y : zb){
  75.             odl[c].pb({dyst[y], u});
  76.         }
  77.     }
  78.  
  79.     sort(odl[c].begin(), odl[c].end());
  80.     int m = odl[c].size();
  81.     pref[c].resize(m);
  82.     suf[c].resize(m);
  83.  
  84.     pref[c][0] = {odl[c][0].ff, odl[c][0].ss, -1LL, -2LL};
  85.     for(int i = 1; i < m; i++){
  86.         ll d = odl[c][i].ff, k = odl[c][i].ss;
  87.         pref[c][i] = pref[c][i - 1]; 
  88.  
  89.         if(k == pref[c][i].k1){
  90.             pref[c][i].v1 = max(pref[c][i].v1, d);
  91.         } else {
  92.             if(d > pref[c][i].v1){
  93.                 pref[c][i].v2 = pref[c][i].v1;
  94.                 pref[c][i].k2 = pref[c][i].k1;
  95.                 pref[c][i].v1 = d;
  96.                 pref[c][i].k1 = k;
  97.             } else if(d > pref[c][i].v2){
  98.                 pref[c][i].v2 = d;
  99.                 pref[c][i].k2 = k;
  100.             }
  101.         }
  102.     }
  103.  
  104.     suf[c][m - 1] = {odl[c][m - 1].ff, odl[c][m - 1].ss, INF, -2LL};
  105.     for(int i = m - 2; i >= 0; i--){
  106.         ll d = odl[c][i].ff, k = odl[c][i].ss;
  107.         suf[c][i] = suf[c][i + 1];
  108.  
  109.         if(k == suf[c][i].k1){
  110.             suf[c][i].v1 = min(suf[c][i].v1, d);
  111.         } else {
  112.             if(d < suf[c][i].v1){
  113.                 suf[c][i].v2 = suf[c][i].v1;
  114.                 suf[c][i].k2 = suf[c][i].k1;
  115.                 suf[c][i].v1 = d;
  116.                 suf[c][i].k1 = k;
  117.             } else if(d < suf[c][i].v2){
  118.                 suf[c][i].v2 = d;
  119.                 suf[c][i].k2 = k;
  120.             }
  121.         }
  122.     }
  123.  
  124.     for(pii x : graf[c]){
  125.         if(odw[x.ff]) continue;
  126.         decompose(x.ff);
  127.     }
  128. }
  129.  
  130. ll mniej(ll x, int n){
  131.     ll best = -1;
  132.     for(int c = 1; c <= n; c++){
  133.         if(odl[c].empty()) continue;
  134.         int m = odl[c].size();
  135.         int j = m - 1;
  136.         for(int i = 0; i < m; i++){
  137.             while(j >= 0 && odl[c][i].ff + odl[c][j].ff > x) j--;
  138.             if(j < 0) break;
  139.  
  140.             ll kand = odl[c][i].ff, k = odl[c][i].ss;
  141.             ll partner_d = -1;
  142.  
  143.             if(k != pref[c][j].k1){
  144.                 partner_d = pref[c][j].v1;
  145.             } else if(pref[c][j].v2 != -1){
  146.                 partner_d = pref[c][j].v2;
  147.             }
  148.  
  149.             if(partner_d != -1){
  150.                 best = max(kand + partner_d, best);
  151.             }
  152.         }
  153.     }
  154.     return best;
  155. }
  156.  
  157. ll wiecej(ll x, int n){
  158.     ll best = INF;
  159.     for(int c = 1; c <= n; c++){
  160.         if(odl[c].empty()) continue;
  161.         int m = odl[c].size();
  162.         int j = m - 1;
  163.         for(int i = 0; i < m; i++){
  164.             while(j > 0 && odl[c][i].ff + odl[c][j - 1].ff >= x) j--;
  165.             if(odl[c][i].ff + odl[c][j].ff >= x){
  166.                 ll kand = odl[c][i].ff, k = odl[c][i].ss;
  167.                 ll partner_d = INF;
  168.  
  169.                 if(k != suf[c][j].k1){
  170.                     partner_d = suf[c][j].v1;
  171.                 } else if(suf[c][j].v2 != INF){
  172.                     partner_d = suf[c][j].v2;
  173.                 }
  174.  
  175.                 if(partner_d != INF){
  176.                     best = min(kand + partner_d, best);
  177.                 }
  178.             }
  179.         }
  180.     }
  181.     return best;
  182. }
  183.  
  184. int main(){
  185.     ios_base::sync_with_stdio(0);
  186.     cin.tie(0);
  187.  
  188.     int n, q;
  189.     if (!(cin >> n >> q)) return 0;
  190.  
  191.     for(int i = 1; i < n; i++){
  192.         int a, b; ll c;
  193.         cin >> a >> b >> c;
  194.         graf[a].pb({b, c}); 
  195.         graf[b].pb({a, c});
  196.     }
  197.  
  198.     decompose(1);
  199.  
  200.     vector<pll> przedzialy;
  201.     ll p0 = wiecej(1, n);
  202.  
  203.     if(p0 != INF){
  204.         ll L = (p0 + 1) / 2;
  205.         ll curr = p0;
  206.  
  207.         while(true){
  208.             ll p_prime = mniej(2 * curr, n);
  209.             if(p_prime > curr){
  210.                 curr = p_prime;
  211.             } else {
  212.                 przedzialy.pb({L, curr});
  213.                 ll p_next = wiecej(2 * curr + 1, n);
  214.                 if(p_next == INF) break;
  215.                 L = (p_next + 1) / 2;
  216.                 curr = p_next;
  217.             }
  218.         }
  219.     }
  220.  
  221.     string odp = "";
  222.     while(q--){
  223.         ll K;
  224.         cin >> K;
  225.  
  226.         bool ok = false;
  227.         auto it = upper_bound(przedzialy.begin(), przedzialy.end(), make_pair(K, INF));
  228.         if(it != przedzialy.begin()){
  229.             --it;
  230.             if(K >= it->ff && K <= it->ss){
  231.                 ok = true;
  232.             }
  233.         }
  234.  
  235.         odp += (ok ? "1" : "0");
  236.     }
  237.  
  238.     cout << odp << "\n";
  239.  
  240.     return 0;
  241. }
  242.  
Success #stdin #stdout 0.01s 23304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RgPIQ5
language:
C++ (gcc 8.3)
created:
3 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!