fork 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 = 4e16;
  20.  
  21. ll readll(){
  22.     ll x = 0;
  23.     int c = getchar_unlocked();
  24.     while(c < '0') c = getchar_unlocked();
  25.     while(c >= '0'){
  26.         x = x * 10 + (c - '0');
  27.         c = getchar_unlocked();
  28.     }
  29.     return x;
  30. }
  31.  
  32. vector<pll> graf[N], odl[N];
  33. vi zb;
  34. ll dyst[N];
  35. int podd[N], odw[N];
  36.  
  37.  
  38.  
  39. vector<pair<pll, pll>> pref[N], suf[N];
  40.  
  41. void poddrzewa(int v, int ojc){
  42.     podd[v] = 1;
  43.     for(pll x : graf[v]){
  44.         int u = x.ff;
  45.         if(odw[u] || u == ojc) continue;
  46.         poddrzewa(u, v);
  47.         podd[v] += podd[u];
  48.     }
  49. }
  50.  
  51. int znajdz(int v, int ojc, int r){
  52.     for(pll x : graf[v]){
  53.         int u = x.ff;
  54.         if(odw[u] || u == ojc) continue;
  55.         if(podd[u] > r / 2) return znajdz(u, v, r);
  56.     }
  57.     return v;
  58. }
  59.  
  60. void dfs_policz(int v, int ojc){
  61.     zb.pb(v);
  62.     for(pll x : graf[v]){
  63.         int u = x.ff;
  64.         if(u == ojc || odw[u]) continue;
  65.         dyst[u] = dyst[v] + x.ss;
  66.         dfs_policz(u, v);
  67.     }
  68. }
  69.  
  70. void decompose(int v){
  71.     poddrzewa(v, 0);
  72.     int c = znajdz(v, 0, podd[v]);
  73.     odw[c] = 1; dyst[c] = 0;
  74.     odl[c].pb({0, c});
  75.  
  76.     for(pll x : graf[c]){
  77.         int u = x.ff; ll w = x.ss;
  78.         if(odw[u]) continue;
  79.         dyst[u] = w;
  80.         zb.clear();
  81.         dfs_policz(u, 0);
  82.  
  83.         for(int y : zb){
  84.             odl[c].pb({dyst[y], u});
  85.         }
  86.     }
  87.  
  88.     sort(odl[c].begin(), odl[c].end());
  89.     int m = odl[c].size();
  90.     pref[c].resize(m);
  91.     suf[c].resize(m);
  92.  
  93.     pref[c][0] = {{odl[c][0].ff, odl[c][0].ss}, {-1, -2}};
  94.     for(int i = 1; i < m; i++){
  95.         ll d = odl[c][i].ff, k = odl[c][i].ss;
  96.         pref[c][i] = pref[c][i - 1];
  97.  
  98.         if(k == pref[c][i].ff.ss){
  99.             pref[c][i].ff.ff = max(pref[c][i].ff.ff, d);
  100.         }else{
  101.             if(d > pref[c][i].ff.ff){
  102.                 pref[c][i].ss.ff = pref[c][i].ff.ff;
  103.                 pref[c][i].ss.ss = pref[c][i].ff.ss;
  104.                 pref[c][i].ff.ff = d;
  105.                 pref[c][i].ff.ss = k;
  106.             } else if(d > pref[c][i].ss.ff){
  107.                 pref[c][i].ss.ff = d;
  108.                 pref[c][i].ss.ss = k;
  109.             }
  110.         }
  111.     }
  112.  
  113.     suf[c][m - 1] = {{odl[c][m - 1].ff, odl[c][m - 1].ss}, {INF, -2}};
  114.     for(int i = m - 2; i >= 0; i--){
  115.         ll d = odl[c][i].ff, k = odl[c][i].ss;
  116.         suf[c][i] = suf[c][i + 1];
  117.  
  118.         if(k == suf[c][i].ff.ss){
  119.             suf[c][i].ff.ff = min(suf[c][i].ff.ff, d);
  120.         }else{
  121.             if(d < suf[c][i].ff.ff){
  122.                 suf[c][i].ss.ff = suf[c][i].ff.ff;
  123.                 suf[c][i].ss.ss = suf[c][i].ff.ss;
  124.                 suf[c][i].ff.ff = d;
  125.                 suf[c][i].ff.ss = k;
  126.             } else if(d < suf[c][i].ss.ff){
  127.                 suf[c][i].ss.ff = d;
  128.                 suf[c][i].ss.ss = k;
  129.             }
  130.         }
  131.     }
  132.  
  133.     for(pii x : graf[c]){
  134.         if(odw[x.ff]) continue;
  135.         decompose(x.ff);
  136.     }
  137. }
  138.  
  139. ll mniej(ll x, int n){
  140.     ll best = -1;
  141.     for(int c = 1; c <= n; c++){
  142.         if(odl[c].size() < 2) continue;
  143.         int m = odl[c].size();
  144.         int j = m - 1;
  145.         for(int i = 0; i < m; i++){
  146.             while(j >= 0 && odl[c][i].ff + odl[c][j].ff > x) j--;
  147.             if(j < 0) break;
  148.  
  149.             ll kand = odl[c][i].ff, k = odl[c][i].ss;
  150.             ll dod = -1;
  151.  
  152.             if(k != pref[c][j].ff.ss){
  153.                 dod = pref[c][j].ff.ff;
  154.             }else if(pref[c][j].ss.ff != -1){
  155.                 dod = pref[c][j].ss.ff;
  156.             }
  157.  
  158.             if(dod != -1){
  159.                 best = max(kand + dod, best);
  160.             }
  161.         }
  162.     }
  163.     return best;
  164. }
  165.  
  166. ll wiecej(ll x, int n){
  167.     ll best = INF;
  168.     for(int c = 1; c <= n; c++){
  169.         if(odl[c].size() < 2) continue;
  170.         int m = odl[c].size();
  171.         int j = m - 1;
  172.         for(int i = 0; i < m; i++){
  173.             while(j > 0 && odl[c][i].ff + odl[c][j - 1].ff >= x) j--;
  174.             if(odl[c][i].ff + odl[c][j].ff >= x){
  175.                 ll kand = odl[c][i].ff, k = odl[c][i].ss;
  176.                 ll dod = INF;
  177.  
  178.                 if(k != suf[c][j].ff.ss){
  179.                     dod = suf[c][j].ff.ff;
  180.                 }else if(suf[c][j].ss.ff != INF){
  181.                     dod = suf[c][j].ss.ff;
  182.                 }
  183.  
  184.                 if(dod != INF){
  185.                     best = min(kand + dod, best);
  186.                 }
  187.             }
  188.         }
  189.     }
  190.     return best;
  191. }
  192.  
  193. int main(){
  194. //    ios_base::sync_with_stdio(0);
  195. //    cin.tie(0);
  196.  
  197.     int n = readll(), q = readll();
  198.  
  199.     for(int i = 1; i < n; i++){
  200.         int a = readll(), b = readll(); ll c = readll();
  201.         graf[a].pb({b, c});
  202.         graf[b].pb({a, c});
  203.     }
  204.  
  205.     decompose(1);
  206.  
  207.     vector<pll> przedzialy;
  208.     ll pocz = wiecej(1, n);
  209.  
  210.     ll le = (pocz + 1) / 2;
  211.     ll akt = pocz;
  212.  
  213.     while(true){
  214.         ll best = mniej(2 * akt, n);
  215.         if(best > akt){
  216.             akt = best;
  217.         }else{
  218.             przedzialy.pb({le, akt});
  219.             ll next = wiecej(2 * akt + 1, n);
  220.             if(next == INF) break;
  221.             le = (next + 1) / 2;
  222.             akt = next;
  223.         }
  224.     }
  225.  
  226.     while(q--){
  227.         ll k = readll();
  228.  
  229.         bool ok = false;
  230.         auto it = upper_bound(przedzialy.begin(), przedzialy.end(), make_pair(k, INF));
  231.         if(it != przedzialy.begin()){
  232.             --it;
  233.             if(k >= it->ff && k <= it->ss){
  234.                 ok = true;
  235.             }
  236.         }
  237.  
  238.         if(ok) putchar_unlocked('1');
  239.         else putchar_unlocked('0');
  240.     }
  241.  
  242.  
  243.     return 0;
  244. }
  245.  
Success #stdin #stdout 0.01s 25328KB
comments (?)
stdin
copy 
4 5
1 2 5
2 3 2
3 4 20
3
7
1
9
28
stdout
copy 
11100
https://ideone.com/gSHT29
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!