oj.uz

Submission #498657

# Submission time Handle Problem Language Result Execution time Memory
498657 2021-12-26T04:44:43 Z model_code Paths (RMI21_paths) C++17
36 / 100
 600 ms 25588 KB 
// paths_subtask3_alexandra.cpp

// N * K^2
#include<iostream>
#include<vector>
using namespace std;
int n, k, i, x, y, c, j;
int tcost[2005];
long long djos[2005][2005], dsus[2005][2005], daux[2005][2005], sol;
vector< pair<int, int> > v[2005];
int nxt(int nod, int t, int i) {
    if (i == v[nod].size() - 1) {
        return 0;
    }
    if (v[nod][i + 1].first != t) {
        return v[nod][i + 1].first;
    }
    if (i + 1 != v[nod].size() - 1) {
        return v[nod][i + 2].first;
    }
    return 0;
}
int prv(int nod, int t, int i) {
    if (i == 0) {
        return 0;
    }
    if (v[nod][i - 1].first != t) {
        return v[nod][i - 1].first;
    }
    if (i - 1 != 0) {
        return v[nod][i - 2].first;
    }
    return 0;
}
void dfs(int nod, int t) {
    int i, j, jj, fiu;
    for (i = 0; i < v[nod].size(); i++) {
        fiu = v[nod][i].first;
        if (fiu == t) {
            tcost[nod] = v[nod][i].second;
            continue;
        }
        dfs(fiu, nod);
        for (j = k; j >= 1; j--) {
            for (jj = 1; jj <= j; jj++) {
                djos[nod][j] = max(djos[nod][j], djos[nod][j - jj] + djos[fiu][jj] + v[nod][i].second);
            }
        }
        if (nxt(nod, t, i)) {
            fiu = nxt(nod, t, i);
            for (j = 1; j <= k; j++) {
                dsus[fiu][j] = djos[nod][j];
            }
        }
    }

    for (i = v[nod].size() - 1; i >= 1; i--) {
        fiu = v[nod][i].first;
        if (fiu == t) {
            continue;
        }
        for (j = k; j >= 1; j--) {
            for (jj = 1; jj <= j; jj++) {
                daux[nod][j] = max(daux[nod][j], daux[nod][j - jj] + djos[fiu][jj] + v[nod][i].second);
            }
        }
        if (prv(nod, t, i)) {
            fiu = prv(nod, t, i);
            for (j = k; j >= 1; j--) {
                for (jj = 1; jj <= j; jj++) {
                    dsus[fiu][j] = max(dsus[fiu][j], dsus[fiu][j - jj] + daux[nod][jj]);
                }
            }
        }
    }
}
void dfs2(int nod, int t) {
    int i, j, fiu;
    for (i = k; i >= 1; i--) {
        for (j = 1; j <= i; j++) {
            dsus[nod][i] = max(dsus[nod][i], dsus[nod][i - j] + dsus[t][j]);
        }
        dsus[nod][i] += tcost[nod];
    }
    for (i = 0; i < v[nod].size(); i++) {
        if (v[nod][i].first != t) {
            dfs2(v[nod][i].first, nod);
        }
    }
}
int main() {
    cin>> n >> k;
    for (i = 1; i < n; i++) {
        cin>> x >> y >> c;
        v[x].push_back(make_pair(y, c));
        v[y].push_back(make_pair(x, c));
    }
    dfs(1, 0);
    dfs2(1, 0);
    for (i = 1; i <= n; i++) {
        sol = 0;
        for (j = 0; j <= k; j++) {
            sol = max(sol, djos[i][j] + dsus[i][k - j]);
        }
        cout<< sol <<"\n";
    }
}

Compilation message

Main.cpp: In function 'int nxt(int, int, int)':
Main.cpp:12:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     if (i == v[nod].size() - 1) {
      |         ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     if (i + 1 != v[nod].size() - 1) {
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void dfs(int, int)':
Main.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (i = 0; i < v[nod].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void dfs2(int, int)':
Main.cpp:85:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (i = 0; i < v[nod].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
Main.cpp:78:15: warning: unused variable 'fiu' [-Wunused-variable]
   78 |     int i, j, fiu;
      |               ^~~

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 2064 KB Output is correct
5 Correct 2 ms 1740 KB Output is correct
6 Correct 2 ms 2252 KB Output is correct
7 Correct 2 ms 1996 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 2064 KB Output is correct
5 Correct 2 ms 1740 KB Output is correct
6 Correct 2 ms 2252 KB Output is correct
7 Correct 2 ms 1996 KB Output is correct
8 Correct 33 ms 9292 KB Output is correct
9 Correct 17 ms 10004 KB Output is correct
10 Correct 16 ms 10776 KB Output is correct
11 Correct 27 ms 8252 KB Output is correct
12 Correct 19 ms 11032 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 2064 KB Output is correct
5 Correct 2 ms 1740 KB Output is correct
6 Correct 2 ms 2252 KB Output is correct
7 Correct 2 ms 1996 KB Output is correct
8 Correct 33 ms 9292 KB Output is correct
9 Correct 17 ms 10004 KB Output is correct
10 Correct 16 ms 10776 KB Output is correct
11 Correct 27 ms 8252 KB Output is correct
12 Correct 19 ms 11032 KB Output is correct
13 Execution timed out 1072 ms 25588 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 131 ms 12684 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 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 2064 KB Output is correct
5 Correct 2 ms 1740 KB Output is correct
6 Correct 2 ms 2252 KB Output is correct
7 Correct 2 ms 1996 KB Output is correct
8 Correct 33 ms 9292 KB Output is correct
9 Correct 17 ms 10004 KB Output is correct
10 Correct 16 ms 10776 KB Output is correct
11 Correct 27 ms 8252 KB Output is correct
12 Correct 19 ms 11032 KB Output is correct
13 Execution timed out 1072 ms 25588 KB Time limit exceeded
14 Halted 0 ms 0 KB -