Submission #702781

#	Time	Username	Problem	Language	Result	Execution time	Memory
702781		Nursik	Paths (RMI21_paths)	C++14	36 / 100	1089 ms	18264 KiB

Main

#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
 #include <cstdint>
#include <cassert>
#include <functional>
#include <complex>

using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
 
const ll maxn = 2e3 + 10, maxm = 3e5 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blcok = 400, p2 = 31;
const ld eps = 1e-9;

int n, k;
int x[maxn], y[maxn], c[maxn], used[maxn], sz[maxn];
ll dp[maxn][maxn];
vector<pair<int, int>> g[maxn];
void dfs(int v, int p){
    for (int j = 0; j <= k; ++j){
        dp[v][j] = -1;
    }
    dp[v][0] = 0;
    dp[v][1] = 0;
    sz[v] = 1;
    for (auto to : g[v]){
        if (to.f != p){
            dfs(to.f, v);
            for (int j = min(k, sz[v]); j >= 0; --j){
                if (dp[v][j] != -1){
                    for (int j2 = 1; j2 <= min(k, sz[to.f]); ++j2){
                        if (j + j2 <= k){
                            dp[v][j + j2] = max(dp[v][j + j2], dp[to.f][j2] + c[to.s] + dp[v][j]);
                        }
                    }
                }
            }
            sz[v] += sz[to.f];
        }
    }
   /* if (v == 3){
        cout << dp[v][1] << '\n';
        exit(0);
    }*/
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n; ++i){
        cin >> x[i] >> y[i] >> c[i];
        g[x[i]].pb(mp(y[i], i));
        g[y[i]].pb(mp(x[i], i));
    }
    for (int i = 1; i <= n; ++i){
       // memset(dp, -1, sizeof(dp));
        dfs(i, 0);
        cout << dp[i][k] << " ";
      //  exit(0);
    }
}
/*
*/

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