oj.uz

Submission #51692

# Submission time Handle Problem Language Result Execution time Memory
51692 2018-06-20T04:20:02 Z tmwilliamlin168 Fireworks (APIO16_fireworks) C++14
7 / 100
 2000 ms 655360 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=3e5;
int n, m, p[mxN];
vector<int> adj[mxN];
ll c[mxN], yi0[mxN], yi1[mxN];
vector<ll> pc[mxN];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i=1; i<n+m; ++i) {
		cin >> p[i] >> c[i], --p[i];
		adj[p[i]].push_back(i);
	}
	for(int i=1; i<n; ++i) {
		if(adj[i].size()==1) {
			c[adj[i][0]]+=c[i];
			adj[p[i]].push_back(adj[i][0]);
		}
	}
	for(int i=n+m-1; i>=0; --i) {
		if(adj[i].size()==1&&i)
			continue;
		if(i>=n) {
			yi1[i]=-1;
			pc[i].push_back(0);
			pc[i].push_back(0);
		}
		for(int j : adj[i]) {
			if(!yi0[j])
				continue;
			yi0[i]+=yi0[j];
			yi1[i]+=yi1[j];
			pc[i].insert(pc[i].end(), pc[j].begin(), pc[j].end());
		}
		sort(pc[i].begin(), pc[i].end());
		pc[i].erase(pc[i].begin()-yi1[i]+1, pc[i].end());
		pc[i][-yi1[i]-1]+=c[i];
		pc[i][-yi1[i]]+=c[i];
		yi0[i]+=c[i];
//		cout << yi0[i] << " " << yi1[i] << endl;
	}
	ll ans=yi0[0];
	for(int i=0; i<-yi1[0]; ++i)
		ans+=(yi1[0]+i)*(pc[0][i]-(i?pc[0][i-1]:0));
	cout << ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 15 ms 14564 KB Output is correct
3 Correct 16 ms 14676 KB Output is correct
4 Correct 15 ms 14676 KB Output is correct
5 Correct 14 ms 14696 KB Output is correct
6 Correct 17 ms 14708 KB Output is correct
7 Correct 14 ms 14708 KB Output is correct
8 Correct 14 ms 14712 KB Output is correct
9 Correct 16 ms 14784 KB Output is correct
10 Correct 15 ms 14828 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14848 KB Output is correct
2 Correct 13 ms 14848 KB Output is correct
3 Correct 14 ms 14852 KB Output is correct
4 Execution timed out 2133 ms 655360 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 15 ms 14564 KB Output is correct
3 Correct 16 ms 14676 KB Output is correct
4 Correct 15 ms 14676 KB Output is correct
5 Correct 14 ms 14696 KB Output is correct
6 Correct 17 ms 14708 KB Output is correct
7 Correct 14 ms 14708 KB Output is correct
8 Correct 14 ms 14712 KB Output is correct
9 Correct 16 ms 14784 KB Output is correct
10 Correct 15 ms 14828 KB Output is correct
11 Correct 13 ms 14848 KB Output is correct
12 Correct 13 ms 14848 KB Output is correct
13 Correct 14 ms 14852 KB Output is correct
14 Execution timed out 2133 ms 655360 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 15 ms 14564 KB Output is correct
3 Correct 16 ms 14676 KB Output is correct
4 Correct 15 ms 14676 KB Output is correct
5 Correct 14 ms 14696 KB Output is correct
6 Correct 17 ms 14708 KB Output is correct
7 Correct 14 ms 14708 KB Output is correct
8 Correct 14 ms 14712 KB Output is correct
9 Correct 16 ms 14784 KB Output is correct
10 Correct 15 ms 14828 KB Output is correct
11 Correct 13 ms 14848 KB Output is correct
12 Correct 13 ms 14848 KB Output is correct
13 Correct 14 ms 14852 KB Output is correct
14 Execution timed out 2133 ms 655360 KB Time limit exceeded
15 Halted 0 ms 0 KB -