oj.uz

Submission #81645

# Submission time Handle Problem Language Result Execution time Memory
81645 2018-10-25T22:22:35 Z Plurm Fireworks (APIO16_fireworks) C++11
7 / 100
 24 ms 21724 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> g[300005];
multiset<long long> sack[300005];
int info[300005];
int c[300005];
long long slope[300005];
long long yint[300005];
int sz[300005];
void dfs(int u,int p = -1){
	sz[u] = 1;
	int mindex = -1;
	int mx = 0;
	for(int v : g[u]){
		if(v == p) continue;
		dfs(v,u);
		sz[u] += sz[v];
		if(sz[v] > mx){
			mx = sz[v];
			mindex = v;
		}
	}
	if(mindex == -1){
		info[u] = u;
		sack[u].insert(c[u]);
		sack[u].insert(c[u]);
		yint[u] = (long long)c[u];
		slope[u] = -1ll;
	}else{
		info[u] = info[mindex];
		for(int v : g[u]){
			if(v == p) continue;
			if(v == mindex) continue;
			for(int x : sack[info[v]]){
				sack[info[u]].insert(x);
			}
			yint[info[u]] += yint[info[v]];
			slope[info[u]] += slope[info[v]];
		}
		long long opt = *sack[info[u]].rbegin();
		while(!sack[info[u]].empty() && slope[info[u]] + (int)sack[info[u]].size() >= 0){
			opt = *sack[info[u]].rbegin();
			sack[info[u]].erase(sack[info[u]].find(opt));
		}
		sack[info[u]].insert(opt + (long long)c[u]);
		sack[info[u]].insert(opt + (long long)c[u]);
		yint[info[u]] += (long long)c[u];
	}
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 2; i <= n+m; i++){
		int p;
		scanf("%d%d",&p,c+i);
		g[i].push_back(p);
		g[p].push_back(i);
	}
	dfs(1);
	long long ly = yint[info[1]];
	long long ls = slope[info[1]];
	long long lp = 0ll;
	long long mn = ly;
	for(auto x : sack[info[1]]){
		ly += ls * (x - lp);
		ls++;
		lp = x;
		mn = min(mn,ly);
	}
	printf("%lld\n",mn);
}

Compilation message

fireworks.cpp: In function 'int main()':
fireworks.cpp:52: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:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&p,c+i);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21500 KB Output is correct
2 Correct 19 ms 21688 KB Output is correct
3 Correct 22 ms 21688 KB Output is correct
4 Correct 20 ms 21688 KB Output is correct
5 Correct 24 ms 21688 KB Output is correct
6 Correct 19 ms 21688 KB Output is correct
7 Correct 19 ms 21688 KB Output is correct
8 Correct 19 ms 21688 KB Output is correct
9 Correct 19 ms 21688 KB Output is correct
10 Correct 20 ms 21688 KB Output is correct

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21500 KB Output is correct
2 Correct 19 ms 21688 KB Output is correct
3 Correct 22 ms 21688 KB Output is correct
4 Correct 20 ms 21688 KB Output is correct
5 Correct 24 ms 21688 KB Output is correct
6 Correct 19 ms 21688 KB Output is correct
7 Correct 19 ms 21688 KB Output is correct
8 Correct 19 ms 21688 KB Output is correct
9 Correct 19 ms 21688 KB Output is correct
10 Correct 20 ms 21688 KB Output is correct
11 Incorrect 19 ms 21724 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21500 KB Output is correct
2 Correct 19 ms 21688 KB Output is correct
3 Correct 22 ms 21688 KB Output is correct
4 Correct 20 ms 21688 KB Output is correct
5 Correct 24 ms 21688 KB Output is correct
6 Correct 19 ms 21688 KB Output is correct
7 Correct 19 ms 21688 KB Output is correct
8 Correct 19 ms 21688 KB Output is correct
9 Correct 19 ms 21688 KB Output is correct
10 Correct 20 ms 21688 KB Output is correct
11 Incorrect 19 ms 21724 KB Output isn't correct
12 Halted 0 ms 0 KB -