oj.uz

Submission #744304

# Submission time Handle Problem Language Result Execution time Memory
744304 2023-05-18T11:13:00 Z b00norp Fireworks (APIO16_fireworks) C++14
19 / 100
 29 ms 1876 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e18, N = 305;
vector<array<int, 2> > g[N];
int dp[N][N];

void dfs(int node, int par = -1, int parent_weight = 0)
{
	bool isLeaf = true;
	for(auto [to, wt]: g[node])
	{
		dfs(to, node, wt);
		isLeaf = false;
	}
	// cout << "node = " <<  node << ", parent_weight = " << parent_weight << ", isLeaf = " << isLeaf << "\n";
	if(isLeaf)
	{
		dp[node][parent_weight] = 0;
		return;
	}
	for(int i = 0; i < N; i++)
	{
		dp[node][i] = INF;
	}
	vector<int> holyf(N);
	bool omk = true;
	for(auto [to, temp]: g[node])
	{
		for(int i = 0; i < N - parent_weight; i++)
		{
			holyf[i] = INF;
			for(int j = 0; j < N; j++)
			{
				if(j - i > temp) continue;
				holyf[i] = min(holyf[i], dp[to][j] + abs(j - i));
			}
			if(omk)
			{
				dp[node][i + parent_weight] = holyf[i];
			}
			else
			{
				dp[node][i + parent_weight] += holyf[i];
			}
		}
		omk = false;
	}
}

void Solve() 
{
	int n, m;
	cin >> n >> m;
	for(int i = 2; i <= n + m; i++)
	{
		int par, wt;
		cin >> par >> wt;
		// cout << "edge: {" << par << ", " << i << ", " << wt << "}\n";
		g[par].push_back({i, wt});
	}
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < N; j++)
		{
			dp[i][j] = INF;
		}
	}
	dfs(1);
	// for(int i = 1; i <= 10; i++)
	// {
	// 	for(int j = 0; j <= 20; j++)
	// 	{
	// 		cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << "\n";
	// 	}
	// 	cout << "\n\n\n\n";
	// }
	int ans = INF;
	for(int i = 0; i < N; i++)
	{
		ans = min(ans, dp[1][i]);
	}
	cout << ans << "\n";
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    //cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message

fireworks.cpp: In function 'void dfs(long long int, long long int, long long int)':
fireworks.cpp:14:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |  for(auto [to, wt]: g[node])
      |           ^
fireworks.cpp:31:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |  for(auto [to, temp]: g[node])
      |           ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1876 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 6 ms 980 KB Output is correct
4 Correct 11 ms 980 KB Output is correct
5 Correct 11 ms 1064 KB Output is correct
6 Correct 11 ms 976 KB Output is correct
7 Correct 16 ms 1080 KB Output is correct
8 Correct 16 ms 1072 KB Output is correct
9 Correct 16 ms 972 KB Output is correct
10 Correct 18 ms 980 KB Output is correct
11 Correct 23 ms 1068 KB Output is correct
12 Correct 21 ms 980 KB Output is correct
13 Correct 22 ms 980 KB Output is correct
14 Correct 29 ms 1076 KB Output is correct
15 Correct 27 ms 980 KB Output is correct
16 Correct 25 ms 980 KB Output is correct
17 Correct 27 ms 1060 KB Output is correct
18 Correct 27 ms 980 KB Output is correct
19 Correct 25 ms 976 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1876 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1876 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -