oj.uz

Submission #928278

# Submission time Handle Problem Language Result Execution time Memory
928278 2024-02-16T07:02:42 Z vjudge1 Magic Tree (CEOI19_magictree) C++17
100 / 100
 638 ms 46944 KB 
#include<bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define ll long long
#define maksim gay
#define int ll
#define pb push_back
#define sz(s) (int)s.size()
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define mem(a,i) memset(a,i,sizeof(a))
#define in insert
#define lb lower_bound
#define ub upper_bound

const int MAX=1e5+20;
const int inf=1e10;
const int N=2e5;

int n,m,k;
int d[MAX],w[MAX];
vector<int> g[MAX];
int tin[MAX],tout[MAX],timer;
int ob[MAX];
int s[MAX],big[MAX];
map<int,int> dp[MAX];

void dfs(int v){
  tin[v]=++timer;
  ob[timer]=v;
  big[v]=0;
  s[v]=1;
  for(auto to:g[v]){
    dfs(to);
    s[v]+=s[to];
    if(s[to]>s[big[v]])big[v]=to;
  }
  tout[v]=timer;
}

struct DO{
  int sum,add,er;
  DO(){
    sum=add=er=0;
  }
}t[4*MAX];

void push(int v,int tl,int tr){
  if(t[v].er){
    t[2*v].sum=t[2*v+1].sum=t[2*v].add=t[2*v+1].add=0;
    t[2*v].er=t[2*v+1].er=1;
  }
  t[2*v].add+=t[v].add;
  t[2*v+1].add+=t[v].add;
  int tm=(tr+tl)/2;
  t[2*v].sum+=t[v].add*(tm-tl+1);
  t[2*v+1].sum+=t[v].add*(tr-tm);
  t[v].er=t[v].add=0;
}
 
void update(int v,int tl,int tr,int l,int r,int x){
  if(l>r||tl>r||l>tr)return;
  if(l<=tl&&tr<=r){
    t[v].sum=(tr-tl+1)*x;
    t[v].add=x;
    t[v].er=1;
    return;
  }
  push(v,tl,tr);
  int tm=(tl+tr)/2;
  update(2*v,tl,tm,l,r,x);
  update(2*v+1,tm+1,tr,l,r,x);
  t[v].sum=t[2*v].sum+t[2*v+1].sum;
}
 
void update1(int v,int tl,int tr,int l,int r,int x){
  if(l>r||tl>r||l>tr)return;
  if(l<=tl&&tr<=r){
    t[v].sum+=(tr-tl+1)*x;
    t[v].add+=x;
    return;
  }
  push(v,tl,tr);
  int tm=(tl+tr)/2;
  update1(2*v,tl,tm,l,r,x);
  update1(2*v+1,tm+1,tr,l,r,x);
  t[v].sum=t[2*v].sum+t[2*v+1].sum;
}
 
int get(int v,int tl,int tr,int l,int r){
  if(l>r||tl>r||l>tr)return 0;
  if(l<=tl&&tr<=r){
    return t[v].sum;
  }
  push(v,tl,tr);
  int tm=(tl+tr)/2;
  return get(2*v,tl,tm,l,r)+get(2*v+1,tm+1,tr,l,r);
}

void calc(int v,int keep=1){
  for(auto to:g[v]){
    if(to==big[v])continue;
    calc(to,0);
  }
  if(big[v])calc(big[v],1);
  // cout<<v<<"\n";
  // for(int i=1;i<=k;i++){
  //   cout<<get(1,1,k,i)<<" ";
  // }
  // cout<<"\n";
  for(auto to:g[v]){
    if(to==big[v])continue;
    vector<pii> vec;
    for(pii x:dp[to]){
      int u=x.F;
      int val=x.S;
      vec.pb({u,val});
    }
    int r=k+1;
    for(int i=sz(vec)-1;i>=0;i--){
      int u=vec[i].F;
      int val=vec[i].S;
      update1(1,1,k,u,r-1,val);
      r=u;
    }
  }
  if(d[v]){
    int u=d[v];
    int val=w[v]+get(1,1,k,u,u);
    int l=u,r=k,res=u;
    while(l<=r){
      int m=(l+r)/2;
      if(get(1,1,k,m,m)<=val){
        l=m+1;
        res=m;
      }
      else r=m-1;
    }
    update(1,1,k,u,res,val);
  }
  // cout<<v<<"\n";
  // for(int i=1;i<=k;i++){
  //   cout<<get(1,1,k,i,i)<<" ";
  // }
  // cout<<"\n";
  if(!keep){
    for(int i=tin[v];i<=tout[v];i++){
      int u=ob[i];
      if(d[u]){
        dp[v][d[u]]=get(1,1,k,d[u],d[u]);
      }
    }
    update(1,1,k,1,k,0);
  }
}

// !! 3
// 0 0 0 0 5 5 5 5 5 5 5 
// !! 2
// 0 0 0 0 5 5 5 5 5 5 5 
// !! 5
// 0 0 0 0 1 1 1 1 1 1 1 
// !! 6
// 0 0 0 0 0 0 0 0 0 3 3 
// !! 4
// 0 0 0 0 1 1 1 3 3 4 4 
// !! 1
// 0 0 0 0 6 6 6 8 8 9 9 
// 9


void solve(){
  cin>>n>>m>>k;
  for(int i=2;i<=n;i++){
    int p;
    cin>>p;
    g[p].pb(i);
  }
  for(int i=1;i<=m;i++){
    int v;
    cin>>v;
    cin>>d[v]>>w[v];
  }
  dfs(1);
  calc(1);
  cout<<get(1,1,k,k,k)<<"\n";
}


main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t=1;
  // cin>>t;
  while(t--){
    solve();
  }
}

Compilation message

magictree.cpp:193:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  193 | main(){
      | ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 5 ms 19092 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19036 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 31056 KB Output is correct
2 Correct 122 ms 32412 KB Output is correct
3 Correct 562 ms 44944 KB Output is correct
4 Correct 351 ms 28736 KB Output is correct
5 Correct 405 ms 30608 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19288 KB Output is correct
2 Correct 5 ms 19292 KB Output is correct
3 Correct 4 ms 19292 KB Output is correct
4 Correct 298 ms 41024 KB Output is correct
5 Correct 287 ms 41144 KB Output is correct
6 Correct 392 ms 41136 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 27984 KB Output is correct
2 Correct 63 ms 27136 KB Output is correct
3 Correct 66 ms 32080 KB Output is correct
4 Correct 37 ms 28632 KB Output is correct
5 Correct 43 ms 41040 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 5 ms 19092 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19036 KB Output is correct
10 Correct 114 ms 32084 KB Output is correct
11 Correct 99 ms 30800 KB Output is correct
12 Correct 68 ms 32240 KB Output is correct
13 Correct 56 ms 28620 KB Output is correct
14 Correct 53 ms 41040 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20060 KB Output is correct
2 Correct 35 ms 24384 KB Output is correct
3 Correct 35 ms 24156 KB Output is correct
4 Correct 34 ms 24312 KB Output is correct
5 Correct 15 ms 23256 KB Output is correct
6 Correct 31 ms 27172 KB Output is correct
7 Correct 30 ms 31232 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 5 ms 19092 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19036 KB Output is correct
10 Correct 4 ms 19288 KB Output is correct
11 Correct 5 ms 19292 KB Output is correct
12 Correct 4 ms 19292 KB Output is correct
13 Correct 298 ms 41024 KB Output is correct
14 Correct 287 ms 41144 KB Output is correct
15 Correct 392 ms 41136 KB Output is correct
16 Correct 114 ms 32084 KB Output is correct
17 Correct 99 ms 30800 KB Output is correct
18 Correct 68 ms 32240 KB Output is correct
19 Correct 56 ms 28620 KB Output is correct
20 Correct 53 ms 41040 KB Output is correct
21 Correct 68 ms 23380 KB Output is correct
22 Correct 215 ms 33848 KB Output is correct
23 Correct 351 ms 36252 KB Output is correct
24 Correct 609 ms 46944 KB Output is correct
25 Correct 351 ms 28676 KB Output is correct
26 Correct 459 ms 33928 KB Output is correct
27 Correct 405 ms 35788 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 5 ms 19092 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 5 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19036 KB Output is correct
10 Correct 199 ms 31056 KB Output is correct
11 Correct 122 ms 32412 KB Output is correct
12 Correct 562 ms 44944 KB Output is correct
13 Correct 351 ms 28736 KB Output is correct
14 Correct 405 ms 30608 KB Output is correct
15 Correct 4 ms 19288 KB Output is correct
16 Correct 5 ms 19292 KB Output is correct
17 Correct 4 ms 19292 KB Output is correct
18 Correct 298 ms 41024 KB Output is correct
19 Correct 287 ms 41144 KB Output is correct
20 Correct 392 ms 41136 KB Output is correct
21 Correct 65 ms 27984 KB Output is correct
22 Correct 63 ms 27136 KB Output is correct
23 Correct 66 ms 32080 KB Output is correct
24 Correct 37 ms 28632 KB Output is correct
25 Correct 43 ms 41040 KB Output is correct
26 Correct 114 ms 32084 KB Output is correct
27 Correct 99 ms 30800 KB Output is correct
28 Correct 68 ms 32240 KB Output is correct
29 Correct 56 ms 28620 KB Output is correct
30 Correct 53 ms 41040 KB Output is correct
31 Correct 12 ms 20060 KB Output is correct
32 Correct 35 ms 24384 KB Output is correct
33 Correct 35 ms 24156 KB Output is correct
34 Correct 34 ms 24312 KB Output is correct
35 Correct 15 ms 23256 KB Output is correct
36 Correct 31 ms 27172 KB Output is correct
37 Correct 30 ms 31232 KB Output is correct
38 Correct 68 ms 23380 KB Output is correct
39 Correct 215 ms 33848 KB Output is correct
40 Correct 351 ms 36252 KB Output is correct
41 Correct 609 ms 46944 KB Output is correct
42 Correct 351 ms 28676 KB Output is correct
43 Correct 459 ms 33928 KB Output is correct
44 Correct 405 ms 35788 KB Output is correct
45 Correct 71 ms 23380 KB Output is correct
46 Correct 194 ms 33968 KB Output is correct
47 Correct 359 ms 36032 KB Output is correct
48 Correct 638 ms 46872 KB Output is correct
49 Correct 350 ms 28700 KB Output is correct
50 Correct 440 ms 34044 KB Output is correct
51 Correct 417 ms 35668 KB Output is correct