General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
45631931 Practice:
farmersrice
1076E - 16 GNU C++14 Wrong answer on test 5 15 ms 15532 KB 2018-11-12 20:18:32 2018-11-12 20:18:32
 
 
→ Source
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
//#pragma GCC target ("avx,tune=native")
//Use above if bruteforcing with lots of small operations. Or just use it anytime, there's no downside. AVX is better slightly
/*
by farmersrice
*/
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pair2;
typedef pair<ll, pair<ll, ll> > pair3;
typedef pair<int, pair<int, pair<int, int> > > pair4;
#define MAXN 300013
#define INF 1000000000000000000LL
#define MOD 1000000007LL
#define IINF 1000000000
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

int n, m;
vector<int> adj[MAXN];
ll dist[MAXN];
vector<pair2> query[MAXN];
vector<pair3> lost[MAXN]; //how many were "lost" and need to be picked up on the solve dfs back up?
ll answer[MAXN];

ll curSum;
multiset<pair3> active, spent;

void dfs(int cur, int par) {
	for (int next : adj[cur]) {
		if (next == par) continue;

		dist[next] = dist[cur] + 1;
		dfs(next, cur);
	}
}

void solve(int cur, int par) {
	//cout << "solving " << cur << ' ' << par << endl;
	//Process all queries at current node
	for (pair2 q : query[cur]) {
		active.insert(mp(q.first, mp(cur, q.second)));
		curSum += q.second;
	}

	//Deactivate those invalids
	while (active.size() > 0 && (*((active).begin())).first < dist[cur]) {
		auto it = active.begin();
		spent.insert(*it);
		curSum -= (*it).second.second;
		active.erase(it);
	}

	//Reactivate in case we left some things behind.
	while (spent.size() > 0 && (*((spent).begin())).first >= dist[cur]) {
		auto it = spent.begin();
		active.insert(*it);
		curSum += (*it).second.second;
		spent.erase(it);
	}

	answer[cur] = curSum;

	//DFS
	for (int next : adj[cur]) {
		if (next == par) continue;

		solve(next, cur);
	}

	//erase those queries at current node.
	for (pair2 q : query[cur]) {
		pair3 stored = mp(q.first, mp(cur, q.second));

		if (active.find(stored) != active.end()) {
			active.erase(active.find(stored));
			curSum -= q.second;
		}
		if (spent.find(stored) != spent.end()) {
			spent.erase(spent.find(stored)); //shouldn't happen, obviously we would be active on self... but just in case
		}
	}
}

int main() {
	if (fopen("FILENAME.in", "r")) {
		freopen("FILENAME.in", "r", stdin);
		freopen("FILENAME.out", "w", stdout);
	}
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);

	cin >> n;

	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;

		adj[a].pb(b);
		adj[b].pb(a);
	}

	dfs(0, -1);

	cin >> m;


	for (int i = 0; i < m; i++) {
		int v, d, x;
		cin >> v >> d >> x;
		v--;

		query[v].pb(mp(dist[v] + d, x)); //inclusive
	}

	//cout << "BLEH" << endl;
	curSum = 0;
	solve(0, -1);

	for (int i = 0; i < n; i++) {
		cout << answer[i] << " ";
	}
	cout << endl;
}

//don't do dumb stuff with merge-sort tree like using update when everything is static...

//IF IT'S MATH THE ANSWER IS IN THE GCD, GCD THE INPUTS, OR WHATEVER USE GCD
//CAST .SIZE() TO INT!!!!

//PRO TIP: THE BEST WAY TO SOLVE THE PROBLEM IS TO HAVE THE RIGHT ANSWER!
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details