oj.uz

Submission #702781

# Submission time Handle Problem Language Result Execution time Memory
702781 2023-02-25T07:04:57 Z Nursik Paths (RMI21_paths) C++14
36 / 100
 600 ms 18264 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 4 ms 1264 KB Output is correct
4 Correct 4 ms 1236 KB Output is correct
5 Correct 4 ms 1236 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 4 ms 1152 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 4 ms 1264 KB Output is correct
4 Correct 4 ms 1236 KB Output is correct
5 Correct 4 ms 1236 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 4 ms 1152 KB Output is correct
8 Correct 254 ms 5264 KB Output is correct
9 Correct 178 ms 4916 KB Output is correct
10 Correct 142 ms 4788 KB Output is correct
11 Correct 233 ms 5212 KB Output is correct
12 Correct 234 ms 4948 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 4 ms 1264 KB Output is correct
4 Correct 4 ms 1236 KB Output is correct
5 Correct 4 ms 1236 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 4 ms 1152 KB Output is correct
8 Correct 254 ms 5264 KB Output is correct
9 Correct 178 ms 4916 KB Output is correct
10 Correct 142 ms 4788 KB Output is correct
11 Correct 233 ms 5212 KB Output is correct
12 Correct 234 ms 4948 KB Output is correct
13 Execution timed out 1089 ms 18264 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 2260 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 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 4 ms 1264 KB Output is correct
4 Correct 4 ms 1236 KB Output is correct
5 Correct 4 ms 1236 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 4 ms 1152 KB Output is correct
8 Correct 254 ms 5264 KB Output is correct
9 Correct 178 ms 4916 KB Output is correct
10 Correct 142 ms 4788 KB Output is correct
11 Correct 233 ms 5212 KB Output is correct
12 Correct 234 ms 4948 KB Output is correct
13 Execution timed out 1089 ms 18264 KB Time limit exceeded
14 Halted 0 ms 0 KB -