Submission #834391

#	Time	Username	Problem	Language	Result	Execution time	Memory
834391		MODDI	Fireworks (APIO16_fireworks)	C++14	19 / 100	20 ms	5756 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m;
const int N = 2e5 + 10, M = 3e2 + 10;
vector<pair<ll, ll> > G[N];
ll dp[M][M], out[N];
const ll inf = 1e15; 
void dfs(int node, int parent) {
  if(!out[node]) {
    for(int i = 0; i < M; i++) {
      dp[node][i] = inf;
    }
 
    dp[node][0] = 0;
    return;
  }
 
  for(auto i: G[node]) {
    if(i.first == parent) continue;
    dfs(i.first, node);
    for(int j = 0; j < M; j++) {
      long long mini = INT64_MAX;
      for(int k = 0; k <= j; k++) {
        if(dp[i.first][k] == inf) {
          continue;
        }
 
        mini = min(mini, dp[i.first][k] + abs(i.second - (j - k)));
      }
      dp[node][j] += mini;
    }
  }
}
int main(){
	cin>>n>>m;
	for(int i = 2; i <= n; i++) {
	   long long p, c; cin >> p >> c;
	   G[i].pb({p, c});
	   G[p].pb({i, c});
	   out[p]++;
	}
  
    for(int i = n + 1; i <= n + m; i++) {
    	long long p, c; cin >> p >> c;
    	G[i].push_back({p, c});
    	G[p].push_back({i, c});
    	out[p]++;
  	}
//	cout<<endl;
	dfs(1, 0);
	ll ans = INT64_MAX;
		
	for(int i = 0; i < M; i++) {
	    ans = min(ans, dp[1][i]);
	}
	cout<<ans<<endl;
	return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 19 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45