oj.uz

Submission #105761

# Submission time Handle Problem Language Result Execution time Memory
105761 2019-04-14T09:58:26 Z Pro_ktmr Fireworks (APIO16_fireworks) C++14
0 / 100
 47 ms 14636 KB 
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define MOD 1000000007

int N, M;
vector<pair<int, LL>> edge[300001];
int par[300001];
vector<pair<int, LL>> chi[300001];
vector<pair<int, int>> node;
LL a[300001] ={}, b[300001] ={};

void dfs(int now, int p){
	for(int i=0; i<edge[now].size(); i++){
		if(edge[now][i].first == p) continue;
		chi[now].PB(MP(edge[now][i].first, edge[now][i].second));
		par[edge[now][i].first] = now;
		dfs(edge[now][i].first, now);
	}
}

int d[300001] ={};
int depth(int now){
	if(now == 0) return 0;
	if(d[now] != 0) return d[now];
	return d[now] = depth(par[now]) + 1;
}

LL dp[300][301];
LL solve(int now, int cost){
	if(dp[now][cost] != -1) return dp[now][cost];
	if(chi[now].size() == 0 && cost > 0) return dp[now][cost] = INT_MAX;
	LL ans = 0;
	for(int i=0; i<chi[now].size(); i++){
		LL tmp = LLONG_MAX;
		for(int j=0; j<=300; j++){
			tmp = min(tmp, abs(abs(j-cost)-chi[now][i].second) + solve(chi[now][i].first, j));
		}
		ans += tmp;
	}
	return dp[now][cost] = ans;
}

int main(){
	scanf("%d%d", &N, &M);
	for(int i=0; i<N+M-1; i++){
		int P;
		LL C;
		scanf("%d%lld", &P, &C);
		P--;
		edge[i+1].PB(MP(P, C));
		edge[P].PB(MP(i+1, C));
	}

	par[0] = -1;
	dfs(0, -1);

	for(int i=0; i<N+M; i++){
		for(int j=0; j<=300; j++){
			dp[i][j] = -1;
		}
	}

	LL ans = LLONG_MAX;
	for(int i=0; i<=300; i++){
		ans = min(ans, solve(0,i));
	}
	cout << ans << endl;
}

Compilation message

fireworks.cpp: In function 'void dfs(int, int)':
fireworks.cpp:17:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge[now].size(); i++){
               ~^~~~~~~~~~~~~~~~~
fireworks.cpp: In function 'long long int solve(int, int)':
fireworks.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<chi[now].size(); i++){
               ~^~~~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%lld", &P, &C);
   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 14456 KB Output is correct
2 Correct 27 ms 14464 KB Output is correct
3 Incorrect 47 ms 14636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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