oj.uz

Submission #98185

# Submission time Handle Problem Language Result Execution time Memory
98185 2019-02-21T08:34:16 Z fefe Fireworks (APIO16_fireworks) C++17
7 / 100
 21 ms 16896 KB 
#include<bits/stdc++.h>
#define MAX_N 300005
#define MAX_M 100005
#define pb push_back
#define mp make_pair
#define all(V) (V).begin(),(V).end()
#define reset(V) (V).clear();(V).resize(0);
#define sq(x) ((x)*(x))
#define abs(x) ((x)>0?(x):(-(x)))
#define fi first
#define se second
#define LL_inf (1LL<<60)
#define full_inf 0x7fffffff
#define half_inf 0x3fffffff
#define inf 0x3fffffff
#define MOD 1000000007LL
#define cpx_mod(x) (((LD)(((LL)x.real())%MOD)),((LD)(((LL)x.imag())%MOD)))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
typedef pair<LL,string> pls;
typedef complex<LD> Complex;
typedef long double LD;
LL n,m,ln;
LL loc[MAX_N],base[MAX_N];
priority_queue<pil> pq[MAX_N];
vector<pil> adj[MAX_N],lst;
void merge(LL x,LL y){
	LL p=loc[x],q=loc[y];
	if(pq[q].size()>pq[p].size())	swap(p,q);
	loc[x]=p;base[p]+=base[q];
	while(pq[q].size()){
		pq[p].push(pq[q].top());
		pq[q].pop();
	}
}
void dfs(LL x,LL v){
	loc[x]=ln++;
	for(pil p:adj[x]){
		if(!adj[p.fi].size()){pq[loc[x]].push({p.se,1});pq[loc[x]].push({p.se,-1});}
		else{
			dfs(p.fi,p.se);
			merge(x,p.fi);
		}
	}
	//line-up
	//base[x]+=v;
	reset(lst);
	pil p;
	while(pq[loc[x]].size()){
		p=pq[loc[x]].top();
		lst.pb({p.fi,p.se});
		pq[loc[x]].pop();
	}
	LL sz=lst.size();
	pq[loc[x]].push({lst[sz/2].fi+v,-1});
	pq[loc[x]].push({lst[sz/2-1].fi+v,1});
	for(int i=0;i<sz;i++){
		base[loc[x]]+=max((lst[sz/2].fi-lst[i].fi)*lst[i].se,0LL);
	}
}
int main(){
	LL i,x,v;
	scanf("%lld %lld",&n,&m);n+=m;
	for(i=2;i<=n;i++){
		scanf("%lld %lld",&x,&v);
		adj[x].pb({i,v});
	}
	dfs(1,0);
	printf("%lld\n",base[loc[1]]);
	return 0;
}

Compilation message

fireworks.cpp: In function 'int main()':
fireworks.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&m);n+=m;
  ~~~~~^~~~~~~~~~~~~~~~~~~
fireworks.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&x,&v);
   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16768 KB Output is correct
2 Correct 17 ms 16740 KB Output is correct
3 Correct 21 ms 16768 KB Output is correct
4 Correct 21 ms 16824 KB Output is correct
5 Correct 19 ms 16768 KB Output is correct
6 Correct 19 ms 16768 KB Output is correct
7 Correct 18 ms 16768 KB Output is correct
8 Correct 17 ms 16768 KB Output is correct
9 Correct 21 ms 16768 KB Output is correct
10 Correct 19 ms 16896 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16768 KB Output is correct
2 Correct 18 ms 16768 KB Output is correct
3 Incorrect 17 ms 16768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16768 KB Output is correct
2 Correct 17 ms 16740 KB Output is correct
3 Correct 21 ms 16768 KB Output is correct
4 Correct 21 ms 16824 KB Output is correct
5 Correct 19 ms 16768 KB Output is correct
6 Correct 19 ms 16768 KB Output is correct
7 Correct 18 ms 16768 KB Output is correct
8 Correct 17 ms 16768 KB Output is correct
9 Correct 21 ms 16768 KB Output is correct
10 Correct 19 ms 16896 KB Output is correct
11 Correct 16 ms 16768 KB Output is correct
12 Correct 18 ms 16768 KB Output is correct
13 Incorrect 17 ms 16768 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16768 KB Output is correct
2 Correct 17 ms 16740 KB Output is correct
3 Correct 21 ms 16768 KB Output is correct
4 Correct 21 ms 16824 KB Output is correct
5 Correct 19 ms 16768 KB Output is correct
6 Correct 19 ms 16768 KB Output is correct
7 Correct 18 ms 16768 KB Output is correct
8 Correct 17 ms 16768 KB Output is correct
9 Correct 21 ms 16768 KB Output is correct
10 Correct 19 ms 16896 KB Output is correct
11 Correct 16 ms 16768 KB Output is correct
12 Correct 18 ms 16768 KB Output is correct
13 Incorrect 17 ms 16768 KB Output isn't correct
14 Halted 0 ms 0 KB -