oj.uz

Submission #537548

# Submission time Handle Problem Language Result Execution time Memory
537548 2022-03-15T08:15:07 Z zaneyu Paths (RMI21_paths) C++14
19 / 100
 10 ms 4692 KB 
/*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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 1120 KB Output is correct
4 Correct 5 ms 1236 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 1120 KB Output is correct
4 Correct 5 ms 1236 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Runtime error 10 ms 4692 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 1120 KB Output is correct
4 Correct 5 ms 1236 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Runtime error 10 ms 4692 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 1120 KB Output is correct
4 Correct 5 ms 1236 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Runtime error 10 ms 4692 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -