oj.uz

Submission #555179

# Submission time Handle Problem Language Result Execution time Memory
555179 2022-04-30T09:11:40 Z incercari Paths (RMI21_paths) C++14
36 / 100
 600 ms 18252 KB 
#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

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.0 / 8.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1144 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1144 KB Output is correct
8 Correct 6 ms 5204 KB Output is correct
9 Correct 5 ms 4852 KB Output is correct
10 Correct 3 ms 4692 KB Output is correct
11 Correct 75 ms 5148 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1144 KB Output is correct
8 Correct 6 ms 5204 KB Output is correct
9 Correct 5 ms 4852 KB Output is correct
10 Correct 3 ms 4692 KB Output is correct
11 Correct 75 ms 5148 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 51 ms 18252 KB Output is correct
14 Correct 31 ms 10572 KB Output is correct
15 Correct 6 ms 8916 KB Output is correct
16 Execution timed out 1083 ms 15904 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 2132 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 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 1236 KB Output is correct
4 Correct 1 ms 1236 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1144 KB Output is correct
8 Correct 6 ms 5204 KB Output is correct
9 Correct 5 ms 4852 KB Output is correct
10 Correct 3 ms 4692 KB Output is correct
11 Correct 75 ms 5148 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 51 ms 18252 KB Output is correct
14 Correct 31 ms 10572 KB Output is correct
15 Correct 6 ms 8916 KB Output is correct
16 Execution timed out 1083 ms 15904 KB Time limit exceeded
17 Halted 0 ms 0 KB -