Submission #790573

#	Time	Username	Problem	Language	Result	Execution time	Memory
790573		hugo_pm	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	0 / 100	19 ms	29524 KiB

worst_reporter2

#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   = std::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];
	// Calcule les pts bleus
	vector<Croix> cand;
	for (Croix c : src) {
		auto it = dest.lower_bound({c.key, -INF});
		if (it != dest.end()) {
			cand.push_back({c.key, c.val + it->val});
		}
		if (it != dest.begin()) {
			--it;
			cand.push_back({it->key, c.val + it->val});
		}
	}
	// Am├®liore les pts rouges
	int previously = 0;
	for (Croix c : src) {
		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(profile[node].begin()->val, takeNode, dontTake);
	//dbg(node, vector<Croix>(all(profile[node])));
}
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: 0 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21