Submission #555179

#	Time	Username	Problem	Language	Result	Execution time	Memory
555179		incercari	Paths (RMI21_paths)	C++14	36 / 100	1083 ms	18252 KiB

Main

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast", "unroll-loops")

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const ll NMAX = 2001;
const ll MOD = 1000000007;
const ll nr_of_bits = 21;
const ll BLOCK = 420;
const ll KMAX = 2001;

ll dp[NMAX][KMAX];
int n, k;
int sz[NMAX];

vector <pii> v[NMAX];

void adauga(int node, int nou, int y)
{
    int x = nou;
    int s = sz[node] - sz[nou];
    for(int i = min(k, s); i >= 0; i--)
    {
        for(int cant = 1; cant <= min(k - i, sz[x]); cant++)
        {
            ll drum = (cant > 0) * 1LL * y;
            dp[node][i + cant] = max(dp[node][i + cant], dp[node][i] + dp[x][cant] + drum);
        }
    }
}

void copiaza(int node, int son, ll drum){
    for(int i = 1; i <= min(sz[son], k); i++){
        dp[node][i] = dp[son][i] + drum;
    }
}

void calc(int node, int p)
{
    int s = 0;
    int bigSon = 0;
    for(int i = 1; i <= min(sz[node], k); i++)
        dp[node][i] = 0;
    int muchie = 0;
    for(auto x : v[node])
    {
        if(x.first == p)
            continue;
        if(bigSon == 0 || sz[bigSon] < sz[x.first])
        {
            bigSon = x.first;
            muchie = x.second;
        }
    }
    if(bigSon != 0)
    {
        copiaza(node, bigSon, muchie);
    }
    for(auto x : v[node])
    {
        if(x.first == p || x.first == bigSon)
            continue;
        adauga(node, x.first, x.second);
    }
}

int frunze = 0;

void initial(int node, int p){
    if(v[node].size() == 1)
        sz[node] = 1;
    for(auto x : v[node]){
        if(x.first == p) continue;
        initial(x.first, node);
        sz[node] += sz[x.first];
    }
}

void DFS(int node, int p)
{
    int bigSon = 0;
    for(auto x : v[node])
    {
        if(x.first == p)
            continue;
        DFS(x.first, node);
    }
    calc(node, p);
}

ll sol[NMAX];

void Rerooting(int node, int p)
{
    sol[node] = dp[node][k];
    for(auto y : v[node])
    {
        int x = y.first;
        if(x == p)
            continue;
        int sn = sz[node], sx = sz[x];
        sz[node] -= sz[x];
        sz[x] += sz[node];
        calc(node, x);
        if(sz[x] / 2 > sz[node])
            adauga(x, node, y.second);
        else{
            calc(x, -1);
        }
        Rerooting(x, node);
        sz[node] = sn;
        sz[x] = sx;
        calc(x, node);
        if(sz[node] / 2 > sz[x])
            adauga(node, x, y.second);
        else{
            calc(node, -1);
        }
    }
}

int main()
{
//    ifstream cin(".in");
//    ofstream cout(".out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i;
    cin >> n >> k;
    for(i = 1; i < n; i++)
    {
        ll x, y, z;
        cin >> x >> y >> z;
        v[x].push_back({y, z});
        v[y].push_back({x, z});
    }
    initial(1, 0);
    k = min(k, sz[1]);
    DFS(1, 0);
    Rerooting(1, 0);
    for(i = 1; i <= n; i++)
        cout << sol[i] << "\n";
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void calc(int, int)':
Main.cpp:44:9: warning: unused variable 's' [-Wunused-variable]
   44 |     int s = 0;
      |         ^
Main.cpp: In function 'void DFS(int, int)':
Main.cpp:85:9: warning: unused variable 'bigSon' [-Wunused-variable]
   85 |     int bigSon = 0;
      |         ^~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32