oj.uz

Submission #597792

# Submission time Handle Problem Language Result Execution time Memory
597792 2022-07-16T21:56:41 Z ThegeekKnight16 Paths (RMI21_paths) C++17
19 / 100
 600 ms 5404 KB 
#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

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.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 14 ms 1332 KB Output is correct
4 Correct 10 ms 1320 KB Output is correct
5 Correct 15 ms 1620 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct
7 Correct 11 ms 1352 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 14 ms 1332 KB Output is correct
4 Correct 10 ms 1320 KB Output is correct
5 Correct 15 ms 1620 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct
7 Correct 11 ms 1352 KB Output is correct
8 Execution timed out 1074 ms 5404 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 14 ms 1332 KB Output is correct
4 Correct 10 ms 1320 KB Output is correct
5 Correct 15 ms 1620 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct
7 Correct 11 ms 1352 KB Output is correct
8 Execution timed out 1074 ms 5404 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 14 ms 1332 KB Output is correct
4 Correct 10 ms 1320 KB Output is correct
5 Correct 15 ms 1620 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct
7 Correct 11 ms 1352 KB Output is correct
8 Execution timed out 1074 ms 5404 KB Time limit exceeded
9 Halted 0 ms 0 KB -