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 |
|
|
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 |