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;
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 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);
}

//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--;

}

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
?
?
?
?