oj.uz

Submission #208726

# Submission time Handle Problem Language Result Execution time Memory
208726 2020-03-12T05:37:50 Z junodeveloper Fireworks (APIO16_fireworks) C++17
26 / 100
 11 ms 7444 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fi first
#define se second
#define mset(x,y) memset(x,y,sizeof(x))
#define rep(i,a,b) for(int i(a);i<=(b);i++)
#define repr(i,a,b) for(int i(a);i>=(b);i--)
using namespace std;
#ifdef LOCAL
#define dmp(...) _dmp(#__VA_ARGS__, __VA_ARGS__)
#else
#define dmp(...) (__VA_ARGS__)
#endif
template<class TH> void _dmp(const char *sdbg, TH h){cout<<sdbg<<"="<<h<<endl;}
template<class TH, class... TA> void _dmp(const char *sdbg, TH h, TA...a){
while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
}
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
int n,m;
int p[300010],c[300010];
ll ans[300010],up[300010];
vi adj[300010];
priority_queue<ll>* pq[300010];
void merge(int u,int v) {
	while(!pq[v]->empty()) {
		pq[u]->push(pq[v]->top());
		pq[v]->pop();
	}
	ans[u]+=ans[v];
}
void adjust(int u) {
	up[u]+=c[u];
	int top=pq[u]->top();
	pq[u]->pop();
	pq[u]->push(top+c[u]);
}
void debug(int u) {
	priority_queue<int> b;
	cout<<"u:"<<u<<",ans:"<<ans[u]<<",up:"<<up[u]<<",pq:";
	while(!pq[u]->empty())b.push(pq[u]->top()),pq[u]->pop();
	while(!b.empty()) {
		ll it=b.top();b.pop();
		cout<<it<<' ';
		pq[u]->push(it);
	}cout<<endl;
}
void solve(int u) {
	if(adj[u].empty()) {
		pq[u]=new priority_queue<ll>();
		pq[u]->push(0);
		up[u]=0;
		return;
	}
	int mx=-1,id=0;
	vector<ll> ups;
	for(auto& it:adj[u]) {
		solve(it);
		adjust(it);
		if(mx<sz((*pq[it]))) {
			mx=sz((*pq[it]));
			id=it;
		}
		ups.pb(up[it]);
	}
	for(auto& it:adj[u]) {
		if(it==id)continue;
		merge(id,it);
	}
	pq[u]=pq[id];
	ans[u]=ans[id];
	up[u]=up[id];
	sort(all(ups));reverse(all(ups));
	up[u]=1e18;
	for(auto& it:ups) {
		if(it>=pq[id]->top()) {
			up[u]=it;
		} else {
			ans[u]+=pq[id]->top()-it;
			up[u]=pq[id]->top();
			pq[id]->pop();
			pq[id]->push(it);
		}
	}
	//debug(u);
}
void MAIN() {
	int i,j;
	cin>>n>>m;
	for(i=2;i<=n+m;i++) {
		cin>>p[i]>>c[i];
		adj[p[i]].pb(i);
	}
	solve(1);
	cout<<ans[1];
}
int main() {
	ios::sync_with_stdio(false);cin.tie(0);
	int T=1;
	//cin>>T;
	for(int tt=1;tt<=T;tt++) {
		MAIN();
	}
	return 0;
}

Compilation message

fireworks.cpp: In function 'void _dmp(const char*, TH, TA ...)':
fireworks.cpp:20:1: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
 while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
 ^~~~~
fireworks.cpp:20:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
 while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
                                ^~~~
fireworks.cpp: In function 'void MAIN()':
fireworks.cpp:97:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7420 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 10 ms 7416 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 9 ms 7288 KB Output is correct
9 Correct 9 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7420 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct
7 Correct 11 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 9 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Correct 9 ms 7416 KB Output is correct
12 Correct 9 ms 7416 KB Output is correct
13 Correct 9 ms 7416 KB Output is correct
14 Correct 9 ms 7444 KB Output is correct
15 Correct 9 ms 7416 KB Output is correct
16 Correct 9 ms 7416 KB Output is correct
17 Correct 9 ms 7416 KB Output is correct
18 Correct 9 ms 7416 KB Output is correct
19 Correct 9 ms 7416 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7420 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 10 ms 7416 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 9 ms 7288 KB Output is correct
9 Correct 9 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Correct 9 ms 7416 KB Output is correct
12 Correct 9 ms 7420 KB Output is correct
13 Correct 9 ms 7416 KB Output is correct
14 Correct 9 ms 7416 KB Output is correct
15 Correct 9 ms 7416 KB Output is correct
16 Correct 9 ms 7416 KB Output is correct
17 Correct 11 ms 7416 KB Output is correct
18 Correct 9 ms 7416 KB Output is correct
19 Correct 9 ms 7416 KB Output is correct
20 Correct 9 ms 7416 KB Output is correct
21 Correct 9 ms 7416 KB Output is correct
22 Correct 9 ms 7416 KB Output is correct
23 Correct 9 ms 7416 KB Output is correct
24 Correct 9 ms 7444 KB Output is correct
25 Correct 9 ms 7416 KB Output is correct
26 Correct 9 ms 7416 KB Output is correct
27 Correct 9 ms 7416 KB Output is correct
28 Correct 9 ms 7416 KB Output is correct
29 Correct 9 ms 7416 KB Output is correct
30 Incorrect 9 ms 7416 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7420 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 10 ms 7416 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 9 ms 7288 KB Output is correct
9 Correct 9 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Correct 9 ms 7416 KB Output is correct
12 Correct 9 ms 7420 KB Output is correct
13 Correct 9 ms 7416 KB Output is correct
14 Correct 9 ms 7416 KB Output is correct
15 Correct 9 ms 7416 KB Output is correct
16 Correct 9 ms 7416 KB Output is correct
17 Correct 11 ms 7416 KB Output is correct
18 Correct 9 ms 7416 KB Output is correct
19 Correct 9 ms 7416 KB Output is correct
20 Correct 9 ms 7416 KB Output is correct
21 Correct 9 ms 7416 KB Output is correct
22 Correct 9 ms 7416 KB Output is correct
23 Correct 9 ms 7416 KB Output is correct
24 Correct 9 ms 7444 KB Output is correct
25 Correct 9 ms 7416 KB Output is correct
26 Correct 9 ms 7416 KB Output is correct
27 Correct 9 ms 7416 KB Output is correct
28 Correct 9 ms 7416 KB Output is correct
29 Correct 9 ms 7416 KB Output is correct
30 Incorrect 9 ms 7416 KB Output isn't correct
31 Halted 0 ms 0 KB -