Submission #406329

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
406329	2021-05-17T11:38:45 Z	talant117408	Fireworks (APIO16_fireworks)	C++17	26 / 100	20 ms	1056 KB

fireworks

/*
    Code written by Talant I.D.
*/

#include <bits/stdc++.h>
//~ #include <ext/pb_ds/assoc_container.hpp>
 
//~ using namespace __gnu_pbds;
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
//~ typedef tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
 
const int mod = 1e9+7;
 
ll mode(ll a) {
    while (a < 0) {
        a += mod;
    }
    return a % mod;
}
 
ll subt(ll a, ll b) {
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b) {
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b) {
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

const int N = 303;
ll dp[N][N];
vector <pii> graph[N];

void dfs(int v, int p) {
    int children = 0;
    for (auto to : graph[v]) {
        if (to.first == p) {
            continue;
        }
        children++;
        dfs(to.first, v);
    }
    if (!children) {
        dp[v][0] = 0;
    }
    else {
        for (int i = 0; i <= 300; i++) {
            ll res = 0;
            for (auto to : graph[v]) {
                if (to.first == p) continue;
                ll mn = 1e12;
                for (int j = 0; j <= i; j++) {
                    mn = min(mn, dp[to.first][j]+abs(j+to.second-i));
                }
                res += mn;
            }
            dp[v][i] = min(dp[v][i], res);
        }
    }
}

int main() {
    do_not_disturb
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 2; i <= n+m; i++) {
        int p, w;
        cin >> p >> w;
        graph[p].pb(mp(i, w));
        graph[i].pb(mp(p, w));
    }
    
    if (n == 1) {
        ll ans = 9e18;
        for (auto to : graph[1]) {
            ll sum = 0;
            for (auto to2 : graph[1]) {
                sum += abs(to.second-to2.second);
            }
            ans = min(ans, sum);
        }
        cout << ans << endl;
    }
    else if (n+m <= 300) {
        for (int i = 0; i <= 300; i++) {
            for (int j = 0; j <= 300; j++) {
                dp[i][j] = 1e12;
            }
        }
        dfs(1, 1);
        ll ans = 9e18;
        for (int i = 0; i <= 300; i++) {
            ans = min(ans, dp[1][i]);
        }
        cout << ans << endl;
    }
    
    return 0;
}

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	328 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct

Subtask #2
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	972 KB	Output is correct
2	Correct	3 ms	972 KB	Output is correct
3	Correct	5 ms	964 KB	Output is correct
4	Correct	7 ms	1048 KB	Output is correct
5	Correct	8 ms	972 KB	Output is correct
6	Correct	11 ms	972 KB	Output is correct
7	Correct	11 ms	972 KB	Output is correct
8	Correct	12 ms	972 KB	Output is correct
9	Correct	13 ms	1052 KB	Output is correct
10	Correct	14 ms	1052 KB	Output is correct
11	Correct	15 ms	1044 KB	Output is correct
12	Correct	17 ms	1044 KB	Output is correct
13	Correct	18 ms	972 KB	Output is correct
14	Correct	20 ms	1044 KB	Output is correct
15	Correct	19 ms	972 KB	Output is correct
16	Correct	19 ms	1056 KB	Output is correct
17	Correct	19 ms	972 KB	Output is correct
18	Correct	19 ms	972 KB	Output is correct
19	Correct	20 ms	972 KB	Output is correct

Subtask #3
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	328 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	2 ms	972 KB	Output is correct
12	Correct	3 ms	972 KB	Output is correct
13	Correct	5 ms	964 KB	Output is correct
14	Correct	7 ms	1048 KB	Output is correct
15	Correct	8 ms	972 KB	Output is correct
16	Correct	11 ms	972 KB	Output is correct
17	Correct	11 ms	972 KB	Output is correct
18	Correct	12 ms	972 KB	Output is correct
19	Correct	13 ms	1052 KB	Output is correct
20	Correct	14 ms	1052 KB	Output is correct
21	Correct	15 ms	1044 KB	Output is correct
22	Correct	17 ms	1044 KB	Output is correct
23	Correct	18 ms	972 KB	Output is correct
24	Correct	20 ms	1044 KB	Output is correct
25	Correct	19 ms	972 KB	Output is correct
26	Correct	19 ms	1056 KB	Output is correct
27	Correct	19 ms	972 KB	Output is correct
28	Correct	19 ms	972 KB	Output is correct
29	Correct	20 ms	972 KB	Output is correct
30	Incorrect	1 ms	332 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Subtask #4
0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	328 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	2 ms	972 KB	Output is correct
12	Correct	3 ms	972 KB	Output is correct
13	Correct	5 ms	964 KB	Output is correct
14	Correct	7 ms	1048 KB	Output is correct
15	Correct	8 ms	972 KB	Output is correct
16	Correct	11 ms	972 KB	Output is correct
17	Correct	11 ms	972 KB	Output is correct
18	Correct	12 ms	972 KB	Output is correct
19	Correct	13 ms	1052 KB	Output is correct
20	Correct	14 ms	1052 KB	Output is correct
21	Correct	15 ms	1044 KB	Output is correct
22	Correct	17 ms	1044 KB	Output is correct
23	Correct	18 ms	972 KB	Output is correct
24	Correct	20 ms	1044 KB	Output is correct
25	Correct	19 ms	972 KB	Output is correct
26	Correct	19 ms	1056 KB	Output is correct
27	Correct	19 ms	972 KB	Output is correct
28	Correct	19 ms	972 KB	Output is correct
29	Correct	20 ms	972 KB	Output is correct
30	Incorrect	1 ms	332 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Submission #406329

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 19.0 / 19.0

Subtask #3 0 / 29.0

Subtask #4 0 / 45.0

Subtask #1
7.0 / 7.0

Subtask #2
19.0 / 19.0

Subtask #3
0 / 29.0

Subtask #4
0 / 45.0