oj.uz

Submission #597757

# Submission time Handle Problem Language Result Execution time Memory
597757 2022-07-16T19:51:06 Z ThegeekKnight16 Paths (RMI21_paths) C++17
0 / 100
 4 ms 2104 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 10;
int dp[MAXN][MAXN];
// ficar de olho no cache
int dp2[MAXN][MAXN]; 
vector<int> grafo[MAXN], 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] = 0;
    
    for (int i = 0; i < grafo[v].size(); i++)
    {
        int viz = grafo[v][i];
        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] = 0;
    
    for (int i = 1; i <= grafo[v].size(); i++)
    {
        int viz = grafo[v][i-1];
        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] = 0;
        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, 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

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 2104 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -