Submission #597792

#	Time	Username	Problem	Language	Result	Execution time	Memory
597792		ThegeekKnight16	Paths (RMI21_paths)	C++17	19 / 100	1074 ms	5404 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 10;
long long int dp[MAXN][MAXN];
// ficar de olho no cache
long long int dp2[MAXN][MAXN]; 
vector<int> grafo[MAXN];
vector<long long int> pesos[MAXN];
int pai[MAXN], pesoPai[MAXN], Marc[MAXN];
 
void dfs(int v, int K) 
{
    Marc[v] = 1;
    for (int k = 0; k <= K; k++) dp[v][k] = 0LL;
    
    for (int i = 0; i < grafo[v].size(); i++)
    {
        int viz = grafo[v][i];
        long long int p = pesos[v][i];
        if (Marc[viz] == 1) continue;
        pai[viz] = v; pesoPai[viz] = p;
        dfs(viz, K);
    }
    
    for (int k = 0; k <= K; k++) dp2[grafo[v].size()][k] = 0LL;
    
    for (int i = 1; i <= grafo[v].size(); i++)
    {
        int viz = grafo[v][i-1];
        long long int p = pesos[v][i-1];
        if (pai[v] == viz) 
        {
            for (int k = 0; k <= K; k++) dp2[i][k] = dp2[i-1][k];
            continue;
        }
        //cerr << "v: " << v << ", testando viz: " << viz << '\n';
        
        dp2[i][0] = 0LL;
        for (int k = 1; k <= K; k++) 
        {
            dp2[i][k] = dp2[i-1][k];
            for (int q = 1; q <= k; q++) dp2[i][k] = max(dp2[i][k], dp2[i-1][k - q] + dp[viz][q] + p);
        }
    }
    //cerr << "v: " << v << '\n';
    for (int k = 1; k <= K; k++) {dp[v][k] = dp2[grafo[v].size()][k]; /*cerr << dp[v][k] << " ";*/}
    //cerr << '\n';
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K;
    cin >> N >> K;
    for (int i = 1; i < N; i++)
    {
        int X, Y;
      	long long int P;
        cin >> X >> Y >> P;
        grafo[X].push_back(Y);
        pesos[X].push_back(P);
        grafo[Y].push_back(X);
        pesos[Y].push_back(P);
    }
    for (int i = 1; i <= N; i++)
    {
        for (int q = 1; q <= N; q++) Marc[q] = 0;
        pai[i] = i; 
        dfs(i, K);
        //cerr << '\n' << '\n';
        cout << dp[i][K] << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < grafo[v].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
Main.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i = 1; i <= grafo[v].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~

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