oj.uz

Submission #523789

# Submission time Handle Problem Language Result Execution time Memory
523789 2022-02-08T07:42:20 Z mansur Fireworks (APIO16_fireworks) C++17
19 / 100
 10 ms 1484 KB 
#include<bits/stdc++.h>	
 
#pragma optimize ("g",on)
#pragma GCC optimize ("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")

//01001101 01100001 01101011 01101000 01100001  01100111 01100001 01111001 

using namespace std;

#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define pb push_back
#define sz(a) a.size()
#define nl '\n'
#define popb pop_back()                                                                   
#define ld double
#define ull unsigned long long
#define ff first                                         
#define ss second  
#define fix fixed << setprecision
#define pii pair<int, int>                          
#define E exit (0)
#define int long long
 
const int inf = 1e15, N = 501, mod = 998244353;                    

double eps = 1e-6;

vector<pii> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

vector<pii> adj[N];

int cnt[N], dp[N][N];

int n, m;

void calc(int u) {
	if (u > n) {
		cnt[u]++;
	}
	for (auto to: adj[u]) {
		calc(to.ff);
		cnt[u] += cnt[to.ff];
	}
}

void dfs(int u) {
	if (u > n) {
		for (int val = 0; val <= 300; val++) dp[u][val] = val;
		return;
	}
	for (auto to: adj[u]) {
	    if (cnt[to.ff]) {
	    	dfs(to.ff);
	    }
	}
	for (int val = 0; val <= 300; val++) {
		dp[u][val] = 0;
		for (auto to: adj[u]) {
			if (!cnt[to.ff]) continue;
			int mn = inf;
			for (int c = 0; c <= val; c++) {
				mn = min(mn, dp[to.ff][val - c] + abs(to.ss - c));
			}
			dp[u][val] += mn;
		}
	}
}

main() {                                                         
	//freopen("F.in", "r", stdin);                                                                                     
	//freopen("F.out", "w", stdout);                                                                                     
	ios_base::sync_with_stdio(NULL);                                                                                       
	cin.tie(NULL);
	cin >> n >> m;
	vector<int> s;
	for (int i = 2; i <= n + m; i++) {
		int p, c;
		cin >> p >> c;
		adj[p].pb({i, c});
	}
	calc(1);
	dfs(1);
	int ans = inf;
	for (int val = 0; val <= 300; val++) ans = min(ans, dp[1][val]);
	cout << ans;
}

Compilation message

fireworks.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize ("g",on)
      | 
fireworks.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 | main() {
      | ^~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 844 KB Output is correct
7 Correct 6 ms 844 KB Output is correct
8 Correct 6 ms 1004 KB Output is correct
9 Correct 8 ms 1044 KB Output is correct
10 Correct 7 ms 1100 KB Output is correct
11 Correct 8 ms 1204 KB Output is correct
12 Correct 8 ms 1356 KB Output is correct
13 Correct 9 ms 1356 KB Output is correct
14 Correct 10 ms 1484 KB Output is correct
15 Correct 10 ms 1484 KB Output is correct
16 Correct 10 ms 1484 KB Output is correct
17 Correct 10 ms 1404 KB Output is correct
18 Correct 10 ms 1472 KB Output is correct
19 Correct 10 ms 1468 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -