oj.uz

Submission #702783

# Submission time Handle Problem Language Result Execution time Memory
702783 2023-02-25T07:10:12 Z Nursik Paths (RMI21_paths) C++14
36 / 100
 600 ms 18132 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]);
                        }
                        else{
                            break;
                        }
                    }
                }
            }
            sz[v] += sz[to.f];
        }
    }
}
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){
        dfs(i, 0);
        cout << dp[i][k] << " ";
    }
}
/*
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 340 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 1 ms 340 KB Output is correct
3 Correct 3 ms 1252 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 3 ms 1236 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 1 ms 340 KB Output is correct
3 Correct 3 ms 1252 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 202 ms 5232 KB Output is correct
9 Correct 187 ms 4888 KB Output is correct
10 Correct 150 ms 4776 KB Output is correct
11 Correct 201 ms 5212 KB Output is correct
12 Correct 175 ms 5072 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 1 ms 340 KB Output is correct
3 Correct 3 ms 1252 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 202 ms 5232 KB Output is correct
9 Correct 187 ms 4888 KB Output is correct
10 Correct 150 ms 4776 KB Output is correct
11 Correct 201 ms 5212 KB Output is correct
12 Correct 175 ms 5072 KB Output is correct
13 Execution timed out 1051 ms 18132 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 1 ms 340 KB Output is correct
3 Correct 3 ms 1252 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 202 ms 5232 KB Output is correct
9 Correct 187 ms 4888 KB Output is correct
10 Correct 150 ms 4776 KB Output is correct
11 Correct 201 ms 5212 KB Output is correct
12 Correct 175 ms 5072 KB Output is correct
13 Execution timed out 1051 ms 18132 KB Time limit exceeded
14 Halted 0 ms 0 KB -