This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
int v[DIM],cost[DIM],d[DIM],a[DIM],w[DIM];
long long dp[DIM][1010];
vector <int> L[DIM];
map <int,long long> s[DIM];
set <int> aux;
int n,m,k,i,j,x,y;
void dfs (int nod, int tata){
int ok = 0;
for (auto vecin : L[nod])
if (vecin != tata){
ok = 1;
dfs (vecin,nod);
}
for (auto vecin : L[nod]){
if (vecin == tata)
continue;
if (s[nod].size() < s[vecin].size())
swap(s[nod],s[vecin]);
for (auto it : s[vecin])
s[nod][it.first] += it.second;
}
if (v[nod]){
long long val = cost[nod];
s[nod][v[nod]] += val;
while (val > 0){
map <int,long long> :: iterator it = s[nod].upper_bound(v[nod]);
if (it == s[nod].end())
break;
val -= it->second;
if (val > 0)
s[nod].erase(it);
else s[nod][it->first] = -val;
}
}
}
int cautare_binara (int v[], int n, int val){
int st = 1, dr = n;
while (st <= dr){
int mid = (st+dr)>>1;
if (v[mid] == val)
return mid;
if (v[mid] < val)
st = mid+1;
else dr = mid-1;
}
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>m>>k;
int ok2 = 1; /// cazul cu lant
for (i=2;i<=n;i++){
cin>>x;
L[x].push_back(i);
L[i].push_back(x);
if (x != i-1)
ok2 = 0;
}
int ok = 1; long long sum = 0;
for (i=1;i<=m;i++){
cin>>x;
cin>>v[x]>>cost[x];
if (L[x].size() > 1)
ok = 0;
sum += cost[x];
if (cost[x] != 1)
ok2 = 0;
}
if (ok){
cout<<sum;
return 0;
}
if (ok2){
int el = 0;
for (i=1;i<=n;i++)
if (v[i])
a[++el] = v[i];
reverse (a+1,a+el+1);
int sz = 0;
for (i=1;i<=el;i++){
int st = 1, dr = sz;
while (st <= dr){
int mid = (st+dr)>>1;
if (a[d[mid]] <= a[i])
st = mid+1;
else dr = mid-1;
}
if (st == sz+1)
sz++;
d[st] = i;
}
cout<<sz;
return 0;
}
/// normalizez v urii
int el = 0;
for (i=1;i<=n;i++)
if (v[i])
w[++el] = v[i];
sort (w+1,w+el+1);
int el2 = 1;
for (i=2;i<=m;i++)
if (w[i] != w[i-1])
w[++el2] = w[i];
el = el2;
for (i=1;i<=n;i++){
if (!v[i])
continue;
int val = v[i];
v[i] = cautare_binara (w,el,val);
}
k = el;
dfs (1,0);
long long sol = 0;
for (auto it : s[1])
sol += it.second;
cout<<sol;
return 0;
}
Compilation message (stderr)
magictree.cpp: In function 'void dfs(int, int)':
magictree.cpp:14:9: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
14 | int ok = 0;
| ^~
magictree.cpp: In function 'int cautare_binara(int*, int, int)':
magictree.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
66 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |