oj.uz

Submission #711810

# Submission time Handle Problem Language Result Execution time Memory
711810 2023-03-17T14:31:34 Z SA01 Fireworks (APIO16_fireworks) C++14
26 / 100
 1 ms 596 KB 
#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt")

using ll = long long int;
using ull = unsigned long long int;
using vi = vector<ll>;
using ii = pair<ll,ll>;
using vii = vector<ii>;
using ld = long double;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree < T, null_type, less<T>,
rb_tree_tag,
tree_order_statistics_node_update >;

#ifdef SA_DEBUG
template <class T>
void print(T a) {cerr << a << endl;}
template <class T, class... V> 
void print(T a, V... b) {cerr << a << ", "; print(b...);}
#define dbg(...) cerr << "[" << __LINE__ << "] " << #__VA_ARGS__ << " :: ", print(__VA_ARGS__)
#else
#define dbg(...) 7
#endif

#define eb emplace_back
#define fi first
#define se second

const ll INFL = 1e18;
const int INF = 1e9;
const double PI = acos(-1);
const ll mod = 1e9+7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T, class V> 
ostream& operator << (ostream &s, pair<T, V> a){
	s << a.fi << ' ' << a.se; return s;
}

template<class T, class V> 
istream& operator >> (istream &s, pair<T, V> &a){
	s >> a.fi >> a.se; return s;
}

template<class T> 
ostream& operator << (ostream &s, vector<T> a){
	for(int i = 0; i < (int)a.size(); i++){
		if(i > 0)s << ' ' ; 
		s << a[i];
	} return s;
}

template<class T> 
istream& operator >> (istream &s, vector<T> &a){
	for(T &x : a)s >> x; 
	return s;
}

template<class T> 
void input(T a[], int l, int r, istream &s = cin){
	while(l <= r)s >> a[l++];
}

template<class T> 
void output(T a[], int l, int r, bool en = true, ostream &s = cout){
	while(l <= r){ s << a[l++];
		if(l <= r) s << ' ';
	} if(en)s << "\n";
}



const int N = 2e3+3, K = 17, M = 2e5 + 5;
//====================================================================//

template< typename T >
struct SlopeTrick {
  T INF = numeric_limits< T >::max() / 3;
  T min_f, add_l, add_r;
  priority_queue< T, vector< T >, less<> > L;
  priority_queue< T, vector< T >, greater<> > R;
  void push_R(const T &a) { R.push(a - add_r); }
  T top_R() const { return R.top() + add_r; }
  T pop_R() { T val=top_R(); R.pop(); return val;}
  void push_L(const T &a) { L.push(a - add_l); }
  T top_L() const { return L.top() + add_l; }
  T pop_L() { T val=top_L(); L.pop(); return val;}
public:
  SlopeTrick() : min_f(0), add_l(0), add_r(0) {
    L.push(-INF); R.push(INF);
  }
  // f(x) += a
  void add_all(const T &a) {
    min_f += a;
  }
  // add \_ ; f(x) += max(a - x, 0)
  void add_a_minus_x(const T &a) {
    if (a > top_R()) {
      min_f+=a-top_R(); push_L(pop_R());push_R(a);
    } else {
      push_L(a);
    }
  }
  // add _/ ; f(x) += max(x - a, 0)
  void add_x_minus_a(const T &a) {
    if (top_L() > a) {
      min_f+=top_L()-a;push_R(pop_L());push_L(a);
    } else {
      push_R(a);
    }
  }
  // add \/ ; f(x) += max(x - a, 0)
  void add_abs(const T &a) {
    add_a_minus_x(a); add_x_minus_a(a);
  }
  // \/ -> \_ ; f_{new} (x) = min f(y) (y <= x)
  void clear_right(){ while(R.size()>=2)R.pop(); }
  // \/ -> _/ ; f_{new} (x) = min f(y) (y >= x)
  void clear_left(){ while(L.size()>=2) L.pop(); }
  // \/. -> .\/ ; f_{new} (x) = f(x - a)
  void shift(const T &a) { add_l+=a; add_r+=a; }
  T get(const T &x) {
    T ret = min_f;
    if (!L.empty() && x < top_L()) {
      while(!L.empty())ret += max(T(0),pop_L()-x);
    }
    if (!R.empty() && top_R() < x) {
      while(!R.empty())ret += max(T(0),x-pop_R());
    }
    return ret;
  }
  int size(){
		return L.size() + R.size();
	}
};

using stp = SlopeTrick<ll>*;
vii adj[N];
stp merge(stp a, stp b){
	if(a == NULL)return b;
	if(b == NULL)return a;
	if(a -> size() > b -> size())swap(a, b);
	while(a -> L.size() > 1)b -> add_a_minus_x(a -> pop_L());
	while(a -> R.size() > 1)b -> add_x_minus_a(a -> pop_R());
	b -> min_f += a -> min_f;
	return b;
}
stp dfs(int ind){
	stp ret = NULL;
	for(auto [x, y] : adj[ind]){
		stp z = dfs(x);
		if(z == NULL){
			z = new SlopeTrick<ll>();
			z -> add_abs(y);
		}else{
			z -> push_L(z -> pop_L() + y);
			z -> push_R(z -> pop_R() + y);
		}
		ret = merge(ret, z);
	}
	if(ret != NULL){
		ll temp = ret -> top_R();
		ret -> clear_right();
		ret -> push_R(temp);
	}
	return ret;
}

void testcase(){
	int n, m;
	cin >> n >> m;
	for(int i = 2; i <= n + m; i++){
		int a, b;
		cin >> a >> b;
		adj[a].eb(i, b);
	}
	stp ans = dfs(1);
	cout << ans -> min_f << "\n";
}





int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int T = 1;
	
	//cin >> T;
	
	for(int qq = 1; qq <= T; ++qq){
		//cout << "Case #" << qq << ": ";
		testcase();
	}
	return 0;
}
/*
6 1597352862016328480
*/

Compilation message

fireworks.cpp: In function 'SlopeTrick<long long int>* dfs(int)':
fireworks.cpp:158:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  158 |  for(auto [x, y] : adj[ind]){
      |           ^

Subtask #1
7.0 / 7.0

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

Subtask #2
19.0 / 19.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 484 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Runtime error 1 ms 596 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 484 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Runtime error 1 ms 596 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -