oj.uz

Submission #211760

# Submission time Handle Problem Language Result Execution time Memory
211760 2020-03-21T07:43:34 Z kig9981 Fireworks (APIO16_fireworks) C++17
7 / 100
 10 ms 7424 KB 
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;

vector<pair<int,int>> adj[300000];
int parent[300000];
tuple<long long,long long,long long> D[300000];

void dfs(int c)
{
	vector<long long> x(1);
	vector<int> C;
	long long A=0, B=0;
	for(auto[n,w]: adj[c]) {
		dfs(n);
		x.push_back(get<0>(D[n])+=w);
		x.push_back(get<1>(D[n])+=w);
	}
	get<2>(D[c])=0x7fffffffffffffffLL;
	sort(x.begin(),x.end());
	x.resize(unique(x.begin(),x.end())-x.begin());
	C.resize(x.size());
	for(auto[n,w]: adj[c]) {
		auto[l,r,v]=D[n];
		A--; B+=v+l;
		C[lower_bound(x.begin(),x.end(),l)-x.begin()]++;
		C[lower_bound(x.begin(),x.end(),r)-x.begin()]++;
	}
	for(int i=0;i<x.size();i++) {
		A+=C[i];
		B-=x[i]*C[i];
		if(A*x[i]+B<get<2>(D[c])) {
			get<2>(D[c])=A*x[i]+B;
			get<0>(D[c])=get<1>(D[c])=x[i];
		}
		else if(A*x[i]+B==get<2>(D[c])) get<1>(D[c])=x[i];
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M;
	cin>>N>>M; N+=M;
	for(int i=1;i<N;i++) {
		int c;
		cin>>parent[i]>>c;
		adj[--parent[i]].emplace_back(i,c);
	}
	dfs(0);
	cout<<get<2>(D[0])<<'\n';
	return 0;
}

Compilation message

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:31:14: warning: unused variable 'w' [-Wunused-variable]
  for(auto[n,w]: adj[c]) {
              ^
fireworks.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<x.size();i++) {
              ~^~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Incorrect 8 ms 7424 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct
6 Correct 8 ms 7424 KB Output is correct
7 Correct 8 ms 7424 KB Output is correct
8 Correct 8 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct
11 Correct 8 ms 7424 KB Output is correct
12 Correct 10 ms 7424 KB Output is correct
13 Incorrect 8 ms 7424 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct
6 Correct 8 ms 7424 KB Output is correct
7 Correct 8 ms 7424 KB Output is correct
8 Correct 8 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct
11 Correct 8 ms 7424 KB Output is correct
12 Correct 10 ms 7424 KB Output is correct
13 Incorrect 8 ms 7424 KB Output isn't correct
14 Halted 0 ms 0 KB -