Submission #926297

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
926297	2024-02-12T18:35:12 Z	Karoot	Harbingers (CEOI09_harbingers)	C++17	50 / 100	89 ms	25428 KB

harbingers

#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#include <climits>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		if (empty())return linf;
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
	bool eras(ll k, ll m){
		auto it = find({k, m, 0});
		if ((*it).k == k && (*it).m == m){
			erase(it);
			return true;
		}
		return false;
	}
};

const int MAXN = 1e5+4;

LineContainer LC;


vector<int> children[MAXN];
ll d[MAXN];
vector<pair<int, int>> adj[MAXN];
ll w[MAXN], s[MAXN];

ll dp[MAXN];

void buildTree(int node, int parent, ll w){
	d[node] = w;
	for (auto p : adj[node]){
		if (p.first != parent){
			children[node].push_back(p.first);
			buildTree(p.first, node, w+p.second);
		}
	}
}


void dfs(int node){
	if (node == 0){
		dp[node] = 0;
	} else {
		dp[node] = -LC.query(w[node]) + s[node] + d[node]*w[node];
	}
	
	for (int x : children[node]){
		LC.add(d[node], -dp[node]);
		dfs(x);
	}
	//cout << node << ": " << endl;
	LC.eras(d[node], -dp[node]);
}


int main(){
    scoobydoobydoo();
	int n; cin >> n;
	for (int i = 0; i < n-1; i++){
		ll a, b, w; cin >> a >> b >> w;
		a--; b--;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}

	buildTree(0, 0, 0);

	for (int i = 1; i < n; i++){
		cin >> s[i] >> w[i];
	}

	dfs(0);

	//for (int i = 0; i < n; i++)cout << i << ": " << d[i] << endl;


	for (int i = 1; i < n; i++)cout << dp[i] << " ";
	cout << endl;





    return 0;
}

Subtask #1

50.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	8028 KB	Output isn't correct
2	Correct	3 ms	8540 KB	Output is correct
3	Correct	43 ms	16216 KB	Output is correct
4	Correct	51 ms	19980 KB	Output is correct
5	Correct	64 ms	22356 KB	Output is correct
6	Correct	84 ms	25428 KB	Output is correct
7	Incorrect	59 ms	16984 KB	Output isn't correct
8	Incorrect	79 ms	23500 KB	Output isn't correct
9	Incorrect	89 ms	22864 KB	Output isn't correct
10	Incorrect	85 ms	24016 KB	Output isn't correct