Submission #537548

#	Time	Username	Problem	Language	Result	Execution time	Memory
537548		zaneyu	Paths (RMI21_paths)	C++14	19 / 100	10 ms	4692 KiB

Main

/*input
11 3
1 2 5
2 3 3
2 6 5
3 4 4
3 5 2
1 7 6
7 8 4
7 9 5
1 10 1
10 11 1
*/
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define MNTO(x,y) x=min(x,y)
#define MXTO(x,y) x=max(x,y)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define ld long double
#define sz(x) (int)x.size()
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
const int maxn=2e3+5;
vector<pii> v[maxn];
ll dp[maxn][maxn];
int k;
int dfs(int u,int p){
    int s=(sz(v[u])==1);
    for(auto x:v[u]){
        if(x.f==p) continue;
        s+=dfs(x.f,u);
        for(int j=min(s,k);j>=0;j--){
            REP1(z,min(s,k)-j){
                MXTO(dp[u][j+z],dp[u][j]+dp[x.f][z]+x.s);
                if(!dp[x.f][z]) break;
            }
        }
    }
    return s;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n;
    cin>>n>>k;
    REP(i,n-1){
        int a,b,c;
        cin>>a>>b>>c;
        --a,--b;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    dfs(0,-1);
    if(n>200) assert(false);
    REP(i,n){
        REP(j,n) REP(a,k+1) dp[j][a]=0;
        dfs(i,-1);
        cout<<dp[i][k]<<'\n';
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32