Submission #968511


Source Code Expand

#include <bits/stdc++.h>
  
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
 
#define pb emplace_back
#define fi first
#define se second

using namespace std;
 
typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
 
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-8;
const ll MOD = 1e9+7;

template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }
ll in(){ ll x; scanf( "%lld" , &x ); return x; }
 
// head

struct Bit{
  vl bit;
  int size;
  void init( int n ){
    size = 1;
    while( size < n ) size *= 2;
    bit = vl( size , 0 );
  }
  void add( int k , ll v ){
    for( int i = k+1; i <= size; i += i & -i ) bit[i-1] += v;
  }
  ll sum( int k ){ // [0,k)
    ll res = 0;
    for( int i = k; i > 0; i -= i & -i ) res += bit[i-1];
    return res;
  }
  ll sum( int l , int r ){ // [l,r)
    return sum( r ) - sum( l );
  }
  ll get( int k ){
    return sum( k+1 ) - sum( k );
  }
  ll update( int k , ll x ){
    add( k , x - get(k) );
  }
};

ll n, X;
vpl G[100010];

Bit bitc;
Bit bits;

bool centroid[100010];
ll subtree_size[100010];

ll ans;

vl vdir;
vl vind;
vl vall;
vl vc;

ll compute_subtree_size( ll v , ll p ){
  ll c = 1;
  YYS( w , G[v] ){
    if( w.fi == p || centroid[w.fi] ) continue;
    c += compute_subtree_size( w.fi , v );
  }
  return subtree_size[v] = c;
}

pl search_centroid( ll v , ll p , ll t ){
  pl res = pl( INFLL , -1 );
  ll s = 1, m = 0;
  YYS( w , G[v] ){
    if( w.fi == p || centroid[w.fi] ) continue;

    res = min( res , search_centroid( w.fi , v , t ) );

    chmax( m , subtree_size[w.fi] );
    s += subtree_size[w.fi];
  }

  chmax( m , t-s );
  chmin( res , pl( m , v ) );
  return res;
}

ll curcnt = 0;
void dfs( ll x , ll p , ll d , bool fst = false ){
  if( !fst ){
    vind.pb( d );
  }
  if( d < X ){
    vc.pb( d );
    vall.pb( d );
  }
  curcnt++;
  YYS( w , G[x] ){
    if( centroid[w.fi] || w.fi == p ) continue;

    dfs( w.fi , x , d + w.se );
  }
}

void solve_subproblem( ll v ){
  compute_subtree_size( v , -1 );
  ll s = search_centroid( v , -1 , subtree_size[v] ).se;
  centroid[s] = true;

  YYS( w , G[s] ){
    if( centroid[w.fi] ) continue;
    solve_subproblem( w.fi );
  }

  vind.clear();
  vdir.clear();
  vall.clear();
  ll use = 0;
  ll all = 0;
  ll cnt = 0;

  ll min_cost = INF;
  if( SZ(G[s]) != n-1 ){
    min_cost = X;
  }
  
  YYS( w , G[s] ){
    if( centroid[w.fi] ) continue;

    chmin( min_cost , w.se );

    vc.clear();
    curcnt = 0;

    vdir.pb( w.se );
    dfs( w.fi , s , w.se , true );

    YYS( w , vc ){
      use += bitc.sum( X - w );
      ans += bits.sum( X - w ) + w * bitc.sum( X - w );
    }

    YYS( w , vc ){
      bitc.add( w , 1 );
      bits.add( w , w );
    }

    all += cnt * curcnt;
    cnt += curcnt;
  }

  ans += ( all - use ) * X;

  YYS( w , vdir ){
    ans += min( min_cost + X , w );
  }
  YYS( w , vind ){
    ans += min( (ll)X , w );
  }
  
  YYS( w , vall ){
    bitc.add( w , -1 );
    bits.add( w , -w );
  }
  
  centroid[s] = false;
}


int main(){

  bitc.init( 100010 );
  bits.init( 100010 );

  n = in();
  X = in();

  REP( i , n-1 ){
    ll a = in() - 1;
    ll b = in() - 1;
    ll c = in();
    G[a].pb( b , c );
    G[b].pb( a , c );
  }

  solve_subproblem( 0 );

  assert( bitc.sum( 100009 ) == 0 );
  assert( bits.sum( 100009 ) == 0 );

  printf( "%lld\n" , ans );

  return 0;
}

Submission Info

Submission Time
Task D - 道路網
User joisino
Language C++14 (GCC 5.4.1)
Score 1200
Code Size 4376 Byte
Status AC
Exec Time 484 ms
Memory 24944 KB

Compile Error

./Main.cpp: In function ‘ll in()’:
./Main.cpp:43:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 ll in(){ ll x; scanf( "%lld" , &x ); return x; }
                                    ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 2
AC × 46
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt
All 00_example_01.txt, 00_example_02.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 20_k-ary_01.txt, 20_k-ary_02.txt, 20_k-ary_03.txt, 20_k-ary_04.txt, 20_k-ary_05.txt, 20_k-ary_06.txt, 20_k-ary_07.txt, 20_k-ary_08.txt, 20_k-ary_09.txt, 20_k-ary_10.txt, 30_star_01.txt, 30_star_02.txt, 30_star_03.txt, 30_star_04.txt, 30_star_05.txt, 40_pseudostar_01.txt, 40_pseudostar_02.txt, 40_pseudostar_04.txt, 40_pseudostar_05.txt, 40_pseudostar_06.txt, 50_line_01.txt, 50_line_02.txt, 50_line_03.txt, 60_max_01.txt, 60_max_02.txt, 60_max_03.txt, 60_max_04.txt, 70_hand_01.txt, 70_hand_02.txt, 71_hand_01.txt, 72_hand_01.txt, 80_kill2X_01.txt, 80_kill2X_02.txt, 80_kill2X_03.txt, 80_kill2X_04.txt, 80_kill2X_05.txt, 80_kill2X_06.txt, 80_kill2X_07.txt, 80_kill2X_08.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 7 ms 4608 KB
00_example_02.txt AC 7 ms 4608 KB
10_rand_01.txt AC 8 ms 4608 KB
10_rand_02.txt AC 8 ms 4736 KB
10_rand_03.txt AC 7 ms 4608 KB
10_rand_04.txt AC 8 ms 4736 KB
10_rand_05.txt AC 8 ms 4736 KB
20_k-ary_01.txt AC 393 ms 12908 KB
20_k-ary_02.txt AC 394 ms 12908 KB
20_k-ary_03.txt AC 396 ms 12908 KB
20_k-ary_04.txt AC 256 ms 13428 KB
20_k-ary_05.txt AC 214 ms 14072 KB
20_k-ary_06.txt AC 126 ms 12740 KB
20_k-ary_07.txt AC 118 ms 13436 KB
20_k-ary_08.txt AC 115 ms 12324 KB
20_k-ary_09.txt AC 109 ms 11940 KB
20_k-ary_10.txt AC 110 ms 11976 KB
30_star_01.txt AC 63 ms 12016 KB
30_star_02.txt AC 64 ms 12016 KB
30_star_03.txt AC 66 ms 12016 KB
30_star_04.txt AC 71 ms 12016 KB
30_star_05.txt AC 82 ms 12400 KB
40_pseudostar_01.txt AC 85 ms 13424 KB
40_pseudostar_02.txt AC 68 ms 12144 KB
40_pseudostar_04.txt AC 78 ms 12276 KB
40_pseudostar_05.txt AC 74 ms 12272 KB
40_pseudostar_06.txt AC 77 ms 12148 KB
50_line_01.txt AC 416 ms 24060 KB
50_line_02.txt AC 398 ms 24060 KB
50_line_03.txt AC 408 ms 23928 KB
60_max_01.txt AC 358 ms 12920 KB
60_max_02.txt AC 361 ms 12648 KB
60_max_03.txt AC 324 ms 12716 KB
60_max_04.txt AC 339 ms 12780 KB
70_hand_01.txt AC 7 ms 4608 KB
70_hand_02.txt AC 7 ms 4608 KB
71_hand_01.txt AC 156 ms 11772 KB
72_hand_01.txt AC 484 ms 24944 KB
80_kill2X_01.txt AC 63 ms 12016 KB
80_kill2X_02.txt AC 63 ms 12016 KB
80_kill2X_03.txt AC 67 ms 12016 KB
80_kill2X_04.txt AC 64 ms 12016 KB
80_kill2X_05.txt AC 63 ms 12016 KB
80_kill2X_06.txt AC 61 ms 11636 KB
80_kill2X_07.txt AC 63 ms 11508 KB
80_kill2X_08.txt AC 62 ms 11636 KB