Submission #37754

#	Time	Username	Problem	Language	Result	Execution time	Memory
37754		imaxblue	Museum (CEOI17_museum)	C++14	100 / 100	346 ms	784976 KiB

museum

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()

int n, k, x, a, b, d, hi[10005], dp[2][10005][10005];
vector<pii> v[10005];
void dfs(int N, int P){
    dp[0][N][1]=dp[1][N][1]=0;
    hi[N]=1;
    int c;
    fox(l, v[N].size()){
        c=v[N][l].x;
        if (c==P) continue;
        dfs(c, N);
        fox1r(l2, hi[N]){
            fox1(l3, hi[c]){
                dp[0][N][l2+l3]=min(dp[0][N][l2+l3], dp[0][N][l2]+dp[0][c][l3]+v[N][l].y*2);
                dp[1][N][l2+l3]=min(dp[1][N][l2+l3], dp[1][N][l2]+dp[0][c][l3]+v[N][l].y*2);
                dp[1][N][l2+l3]=min(dp[1][N][l2+l3], dp[0][N][l2]+dp[1][c][l3]+v[N][l].y);
            }
        }
        hi[N]+=hi[c];
    }
    /*cout << N<< ' ' << hi[N] << endl;
    fox1(l, hi[N]){
        cout << dp[0][N][l] << ' ';
    } cout << endl;*/
}
int main(){
    flood(dp);
    cin >> n >> k >> x;
    fox(l, n-1){
        cin >> a >> b >> d;
        v[a].pb(mp(b, d));
        v[b].pb(mp(a, d));
    }
    dfs(x, -1);
    cout << dp[1][x][k];
    return 0;
}

Compilation message (stderr)

museum.cpp: In function 'void dfs(int, int)':
museum.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
museum.cpp:33:5: note: in expansion of macro 'fox'
     fox(l, v[N].size()){
     ^

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