oj.uz

Submission #790579

# Submission time Handle Problem Language Result Execution time Memory
790579 2023-07-22T21:32:44 Z hugo_pm Worst Reporter 4 (JOI21_worst_reporter4) C++17
14 / 100
 2000 ms 27512 KB 
#include <bits/stdc++.h>
// Begin treap.h
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Croix {
	ll key, val;
	bool operator<(const Croix& oth) const {
		if (key != oth.key)
			return key < oth.key;
		return val < oth.val; // ├á v├®rifier + INF ou -INF dans merge ?
	}
};

string to_string(Croix c) {
	return "(" + to_string(c.key) + ", " + to_string(c.val) + ")";
}

struct Treap { // bourrin
	set<Croix> s;
	size_t size() { return s.size(); }
	void swap(Treap &oth) { return s.swap(oth.s); }
	void clear() { s.clear(); }
	struct iterator {
		using iterator_category = std::bidirectional_iterator_tag;
		using difference_type   = set<Croix>::iterator::difference_type; // ptrdiff_t?
		using value_type        = const Croix;
		using pointer           = set<Croix>::iterator;
		using reference         = const Croix&;

		iterator(pointer ptr) : m_ptr(ptr) {}
		reference operator*() const { return *m_ptr; }
		pointer operator->() { return m_ptr; }
		iterator& operator++() { m_ptr++; return *this; }  
		iterator operator++(int) { iterator tmp = *this; ++(*this); return tmp; }
		iterator& operator--() { m_ptr--; return *this; }  
		iterator operator--(int) { iterator tmp = *this; --(*this); return tmp; }
		friend bool operator== (const iterator& a, const iterator& b) { return a.m_ptr == b.m_ptr; };
		friend bool operator!= (const iterator& a, const iterator& b) { return a.m_ptr != b.m_ptr; };  

		pointer m_ptr;
	};
	iterator begin() { return iterator(s.begin()); }
	iterator end()   { return iterator(s.end()); }
	pair<iterator, bool> insert(Croix c) {
		return s.insert(c);
	}
	void erase(iterator it) {
		s.erase(it.m_ptr);
	}
	iterator lower_bound(Croix c) {
		return s.lower_bound(c);
	}
	void add(ll until, ll delta) {
		vector<Croix> v(s.begin(), s.end());
		for (Croix &c : v) {
			if (c.key > until) break;
			c.val += delta;
		}
		s = set<Croix>(v.begin(), v.end());
	}
};
// End treap.h
#define int long long
using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define sz(v) ((int)((v).size()))

template<typename T>
void chmax(T &x, const T &v) { if (x < v) x = v; }
template<typename T>
void chmin(T &x, const T &v) { if (x > v) x = v; }

using pii = pair<int, int>;
using vi = vector<int>;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
	bool first = true;
	string res = "[";
	for (const auto &x : v) {
		if (!first)
			res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "]";
	return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
	cout << ' ' << to_string(H);
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int INF = 3e18;
const int MAX_N = 2e5 + 5;
int nbNode;
Treap profile[MAX_N];
int costDel[MAX_N], hauteur[MAX_N];
vector<int> children[MAX_N];

void insere(Treap &dest, Croix c) {
	auto it = dest.insert(c).first;
	if (it != dest.end() && c.val <= next(it)->val) {
		dest.erase(it);
	}
	while (it != dest.begin() && prev(it)->val <= c.val) {
		dest.erase(prev(it));
	}
}
void merge(int iDest, int iSrc) {
	if (profile[iDest].size() < profile[iSrc].size()) {
		profile[iDest].swap(profile[iSrc]);
	}
	auto &dest = profile[iDest], &src = profile[iSrc];
	assert(!dest.s.empty());
	// Calcule les pts bleus
	vector<Croix> cand;
	for (Croix c : src) {
		auto it = dest.lower_bound({c.key, -INF});
		int nxRed = (it != dest.end() ? it->val : 0);
		cand.push_back({c.key, c.val + nxRed});
	}
	// Am├®liore les pts rouges
	int previously = 0;
	vector<Croix> revSrc(src.begin(), src.end());
	reverse(all(revSrc));
	for (Croix c : revSrc) {
		dest.add(c.key, c.val - previously);
		previously = c.val;
	}
	src.clear();
	// Insère les pts bleus
	for (Croix c : cand) {
		insere(dest, c);
	}
}

const int FAKE = MAX_N-1;
void dfs(int node) {
	int takeNode = costDel[node];
	int dontTake = 0;
	for (int child : children[node]) {
		dfs(child);
		auto it = profile[child].lower_bound({hauteur[node], -INF});
		if (it != profile[child].end()) {
			takeNode += it->val;
		}
		dontTake += profile[child].begin()->val;
		merge(node, child);
	}
	insere(profile[node], {hauteur[node], takeNode});
	// dbg(node, vector<Croix>(all(profile[node])));
	// dbg(takeNode, dontTake);
	assert(profile[node].begin()->val == max(takeNode, dontTake));
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> nbNode;
	int totCost = 0;
	rep(i, 0, nbNode) {
		int p;
		cin >> p >> hauteur[i] >> costDel[i];
		totCost += costDel[i];
		if (i > 0) {
			children[p-1].push_back(i);
		}
	}
	dfs(0);
	cout << totCost - profile[0].begin()->val << '\n';
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 6 ms 14420 KB Output is correct
5 Correct 494 ms 15176 KB Output is correct
6 Correct 30 ms 14792 KB Output is correct
7 Correct 10 ms 14676 KB Output is correct
8 Correct 483 ms 15312 KB Output is correct
9 Correct 29 ms 14676 KB Output is correct
10 Correct 11 ms 14676 KB Output is correct
11 Correct 9 ms 14680 KB Output is correct
12 Correct 9 ms 15228 KB Output is correct
13 Correct 9 ms 15188 KB Output is correct
14 Correct 10 ms 14948 KB Output is correct
15 Correct 9 ms 14948 KB Output is correct
16 Correct 415 ms 15160 KB Output is correct
17 Correct 26 ms 14676 KB Output is correct
18 Correct 8 ms 14696 KB Output is correct
19 Correct 263 ms 15336 KB Output is correct
20 Correct 19 ms 14932 KB Output is correct
21 Correct 8 ms 14820 KB Output is correct
22 Correct 947 ms 15444 KB Output is correct
23 Correct 31 ms 14676 KB Output is correct
24 Correct 231 ms 15356 KB Output is correct
25 Correct 19 ms 14932 KB Output is correct
26 Correct 10 ms 15188 KB Output is correct
27 Correct 497 ms 15440 KB Output is correct
28 Correct 303 ms 15500 KB Output is correct
29 Correct 145 ms 15652 KB Output is correct
30 Correct 386 ms 15580 KB Output is correct
31 Correct 382 ms 15588 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 6 ms 14420 KB Output is correct
5 Correct 494 ms 15176 KB Output is correct
6 Correct 30 ms 14792 KB Output is correct
7 Correct 10 ms 14676 KB Output is correct
8 Correct 483 ms 15312 KB Output is correct
9 Correct 29 ms 14676 KB Output is correct
10 Correct 11 ms 14676 KB Output is correct
11 Correct 9 ms 14680 KB Output is correct
12 Correct 9 ms 15228 KB Output is correct
13 Correct 9 ms 15188 KB Output is correct
14 Correct 10 ms 14948 KB Output is correct
15 Correct 9 ms 14948 KB Output is correct
16 Correct 415 ms 15160 KB Output is correct
17 Correct 26 ms 14676 KB Output is correct
18 Correct 8 ms 14696 KB Output is correct
19 Correct 263 ms 15336 KB Output is correct
20 Correct 19 ms 14932 KB Output is correct
21 Correct 8 ms 14820 KB Output is correct
22 Correct 947 ms 15444 KB Output is correct
23 Correct 31 ms 14676 KB Output is correct
24 Correct 231 ms 15356 KB Output is correct
25 Correct 19 ms 14932 KB Output is correct
26 Correct 10 ms 15188 KB Output is correct
27 Correct 497 ms 15440 KB Output is correct
28 Correct 303 ms 15500 KB Output is correct
29 Correct 145 ms 15652 KB Output is correct
30 Correct 386 ms 15580 KB Output is correct
31 Correct 382 ms 15588 KB Output is correct
32 Correct 494 ms 15348 KB Output is correct
33 Execution timed out 2051 ms 27512 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 6 ms 14420 KB Output is correct
5 Correct 494 ms 15176 KB Output is correct
6 Correct 30 ms 14792 KB Output is correct
7 Correct 10 ms 14676 KB Output is correct
8 Correct 483 ms 15312 KB Output is correct
9 Correct 29 ms 14676 KB Output is correct
10 Correct 11 ms 14676 KB Output is correct
11 Correct 9 ms 14680 KB Output is correct
12 Correct 9 ms 15228 KB Output is correct
13 Correct 9 ms 15188 KB Output is correct
14 Correct 10 ms 14948 KB Output is correct
15 Correct 9 ms 14948 KB Output is correct
16 Correct 415 ms 15160 KB Output is correct
17 Correct 26 ms 14676 KB Output is correct
18 Correct 8 ms 14696 KB Output is correct
19 Correct 263 ms 15336 KB Output is correct
20 Correct 19 ms 14932 KB Output is correct
21 Correct 8 ms 14820 KB Output is correct
22 Correct 947 ms 15444 KB Output is correct
23 Correct 31 ms 14676 KB Output is correct
24 Correct 231 ms 15356 KB Output is correct
25 Correct 19 ms 14932 KB Output is correct
26 Correct 10 ms 15188 KB Output is correct
27 Correct 497 ms 15440 KB Output is correct
28 Correct 303 ms 15500 KB Output is correct
29 Correct 145 ms 15652 KB Output is correct
30 Correct 386 ms 15580 KB Output is correct
31 Correct 382 ms 15588 KB Output is correct
32 Correct 494 ms 15348 KB Output is correct
33 Execution timed out 2051 ms 27512 KB Time limit exceeded
34 Halted 0 ms 0 KB -