| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 42895 | 2018-03-06T08:02:06 Z | PowerOfNinjaGo | Gap (APIO16_gap) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector< ii > vii;
typedef long long L;
typedef vector< L > vL;
typedef vector< vL > vvL;
typedef vector< vi > vvi;
typedef vector< vii > vvii;
const int inf = 1e9;
const L inf8 = 1e18;
int p[300005], c[300005];
struct node
{
L a, b;
priority_queue<L> *pq;
node operator+(node r)
{
node res;
res.a = a + r.a;
res.b = b + r.b;
if(pq->size()> r.pq->size())
{
res.pq = pq;
while(r.pq->size()> 0)
{
res.pq->push(r.pq->top()); r.pq->pop();
}
}
else
{
res.pq = r.pq;
while(pq->size()> 0)
{
res.pq->push(pq->top()); pq->pop();
}
}
return res;
}
};
node f[300005];
int main()
{
int n, m; scanf("%d %d", &n, &m);
for(int i = 2; i<= n+m; i++) scanf("%d %d", p+i, c+i);
for(int i = 1; i<= n+m; i++)
{
f[i].a = f[i].b = 0;
f[i].pq = new priority_queue<L>;
}
for(int i = n+1; i<= n+m; i++)
{
f[i].a = 1; f[i].b = -c[i];
f[i].pq->push(c[i]); f[i].pq->push(c[i]);
f[p[i]] = f[p[i]]+f[i];
}
for(int i = n; i> 1; i--)
{
while(f[i].a> 1)
{
f[i].b += f[i].pq->top();
f[i].pq->pop();
f[i].a--;
}
L k1 = f[i].pq->top(); f[i].pq->pop();
L k2 = f[i].pq->top(); f[i].pq->pop();
f[i].pq->push(k1+c[i]); f[i].pq->push(k2+c[i]);
f[i].b -= c[i];
f[p[i]] = f[p[i]]+f[i];
}
while(f[1].a> 0)
{
f[1].a--;
f[1].b += f[1].pq->top();
f[1].pq->pop();
}
cout << f[1].b << endl;
return 0;
}