oj.uz

Submission #702784

# Submission time Handle Problem Language Result Execution time Memory
702784 2023-02-25T07:16:17 Z Nursik Paths (RMI21_paths) C++14
48 / 100
 600 ms 25292 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[maxm], y[maxm], c[maxm], used[maxm], sz[maxm];
ll dp[maxn][maxn];
vector<pair<int, int>> g[maxm];
ll dps[maxm], answ[maxm];
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];
        }
    }
}
void dfs2(int v = 1, int p = 0){
    dps[v] = 0;
    for (auto to : g[v]){
        if (to.f != p){
            dfs2(to.f, v);
            dps[v] = max(dps[v], dps[to.f] + c[to.s]);
        }
    }
}
void pdfs2(int v = 1, int p = 0){
    answ[v] = dps[v];
    multiset<ll> setik;
    for (auto to : g[v]){
        setik.insert(dps[to.f] + c[to.s]);
    }
    for (auto to : g[v]){
        if (to.f != p){
            ll prevdp = dps[v], prevdp2 = dps[to.f];
            ll x = dps[to.f] + c[to.s];
            setik.erase(setik.find(x));
            dps[v] = *setik.rbegin();
            dps[to.f] = max(dps[to.f], dps[v] + c[to.s]);
            pdfs2(to.f, v);
            setik.insert(x);
            dps[v] = prevdp;
            dps[to.f] = prevdp2;
        }
    }
}
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));
    }
    if (k == 1){
        dfs2();
        pdfs2();
        for (int i = 1; i <= n; ++i){
            cout << answ[i] << " ";
        }
        exit(0);
    }
    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 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 7 ms 8148 KB Output is correct
4 Correct 7 ms 8276 KB Output is correct
5 Correct 7 ms 8148 KB Output is correct
6 Correct 6 ms 8148 KB Output is correct
7 Correct 7 ms 8276 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 7 ms 8148 KB Output is correct
4 Correct 7 ms 8276 KB Output is correct
5 Correct 7 ms 8148 KB Output is correct
6 Correct 6 ms 8148 KB Output is correct
7 Correct 7 ms 8276 KB Output is correct
8 Correct 207 ms 12268 KB Output is correct
9 Correct 169 ms 11888 KB Output is correct
10 Correct 145 ms 11772 KB Output is correct
11 Correct 222 ms 12216 KB Output is correct
12 Correct 178 ms 12068 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 7 ms 8148 KB Output is correct
4 Correct 7 ms 8276 KB Output is correct
5 Correct 7 ms 8148 KB Output is correct
6 Correct 6 ms 8148 KB Output is correct
7 Correct 7 ms 8276 KB Output is correct
8 Correct 207 ms 12268 KB Output is correct
9 Correct 169 ms 11888 KB Output is correct
10 Correct 145 ms 11772 KB Output is correct
11 Correct 222 ms 12216 KB Output is correct
12 Correct 178 ms 12068 KB Output is correct
13 Execution timed out 1032 ms 25292 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 16812 KB Output is correct
2 Correct 88 ms 22544 KB Output is correct
3 Correct 70 ms 16708 KB Output is correct
4 Correct 89 ms 17740 KB Output is correct
5 Correct 87 ms 19300 KB Output is correct
6 Correct 91 ms 18376 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 7 ms 8148 KB Output is correct
4 Correct 7 ms 8276 KB Output is correct
5 Correct 7 ms 8148 KB Output is correct
6 Correct 6 ms 8148 KB Output is correct
7 Correct 7 ms 8276 KB Output is correct
8 Correct 207 ms 12268 KB Output is correct
9 Correct 169 ms 11888 KB Output is correct
10 Correct 145 ms 11772 KB Output is correct
11 Correct 222 ms 12216 KB Output is correct
12 Correct 178 ms 12068 KB Output is correct
13 Execution timed out 1032 ms 25292 KB Time limit exceeded
14 Halted 0 ms 0 KB -