Submission #283089

#	Time	Username	Problem	Language	Result	Execution time	Memory
283089		infinite_iq	Museum (CEOI17_museum)	C++14	80 / 100	3148 ms	745720 KiB

museum

    #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
    #include <bits/stdc++.h>
    using namespace std;
    #define sqr 340
    #define mp make_pair
    #define mid (l+r)/2
    #define le node * 2 
    #define ri node * 2 + 1 
    #define pb push_back
    #define ppb pop_back
    #define fi first
    #define se second
    #define lb lower_bound
    #define ub upper_bound
    #define ins insert
    #define era erase
    #define C continue
    #define mem(dp,i) memset(dp,i,sizeof(dp))
    #define mset multiset
    #define all(x) x.begin(), x.end()
    #define gc getchar_unlocked
    typedef long long ll;
    typedef short int si;
    typedef long double ld;
    typedef pair<int,int> pi;
    typedef pair<ll,ll> pll;
    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pi> vpi;
    typedef vector<pll> vpll;
    typedef pair<double,ll>pdi;
    const ll inf=1e18;
    const ll mod=998244353;
    const ld Pi=acos(-1) ;
    int n , k , root ;
    vpi v [10009] ;
    int dp [10009][10009][2] , sz [10009] ;
    int Min ( int x , int y ) {
            x = ( x == -1 ? 1e9 : x ) ;
            return min ( x , y ) ;
    }
    void dfs ( int node , int p ) {
            sz [node] = 1 ;
            for ( auto U : v [node] ) {
                    int u = U .fi ;
                    if ( u == p ) C ;
                    dfs ( u , node ) ;
                    sz [node] += sz [u] ;
            }
            int crnt = 1 ;
            dp [node][1][0] = dp [node][1][1] = 0 ;
            for ( auto U : v [node] ) {
                    int u = U .fi , cost = U .se ;
                    if ( u == p ) C ;
                    crnt += sz [u] ;
                    for ( int i = min ( k , crnt ) ; i >= 2 ; i -- ) {
                            for ( int j = 1 ; j <= min ( i - 1 , sz [u] ) ; j ++ ) {
                                    if (    dp [node][i-j][0] != -1 ) {
                                            dp [node][i][0] = Min ( dp [node][i][0] , dp [node][i-j][0] + dp [u][j][1] + cost * 2 ) ;
                                    }
                                    if (    dp [node][i-j][1] != -1 ) {
                                            dp [node][i][1] = Min ( dp [node][i][1] , dp [node][i-j][1] + dp [u][j][1] + cost * 2 ) ;
                                            dp [node][i][0] = Min ( dp [node][i][0] , dp [node][i-j][1] + dp [u][j][0] + cost ) ;
                                    }
                            }
                    }
            }
    }
    int main () {
            cin >> n >> k >> root ;
            root -- ;
            for ( int i = 0 ; i < n - 1 ; i ++ ) {
                    int a , b , c ;
                    scanf ("%d%d%d",&a ,&b ,&c ) ;
                    a -- , b -- ;
                    v [a] .pb ( { b , c } ) ;
                    v [b] .pb ( { a , c } ) ;
            }
            for ( int i = 0 ; i < n ; i ++ ) {
                    for ( int j = 1 ; j <= k ; j ++ ) {
                            dp [i][j][0] = dp [i][j][1] = -1 ;
                    }
            }
            dfs ( root , root ) ;
            cout << min ( dp [root][k][0] , dp [root][k][1] ) << endl ;
    }

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:74:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |                     scanf ("%d%d%d",&a ,&b ,&c ) ;
      |                     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 0 / 20