oj.uz

Submission #909222

# Submission time Handle Problem Language Result Execution time Memory
909222 2024-01-17T06:22:18 Z ibm2006 Magic Tree (CEOI19_magictree) C++17
47 / 100
 2000 ms 906944 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,i,j,k,l,r,x,y,z,w,s,t,b[1100000],dp[110000][1100],h[1100000],m;
vector<ll> v[1100000],u;
pair<ll,ll> a[1100000];
void f(ll x,ll y)
{
    ll i,j;
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==y)
            continue;
        f(v[x][i],x);
    }
    for(i=1;i<=k;i++)
    {
        s=0;
        for(j=0;j<h[x];j++)
        {
            if(v[x][j]==y)
                continue;
            if(i==1)
                b[j]=0;
            b[j]=max(b[j],dp[v[x][j]][i]);
            s+=b[j];
        }
        if(i==a[x].first)
            s+=a[x].second;
        dp[x][i]=s;
    }
}
int main()
{
    scanf("%lld %lld %lld",&n,&m,&k);
    for(i=2;i<=n;i++)
    {
        scanf("%lld",&x);
        y=i;
        v[x].push_back(y);
        v[y].push_back(x);
        h[x]++;
        h[y]++;
    }
    for(i=1;i<=m;i++)
    {
        scanf("%lld %lld %lld",&x,&y,&z);
        u.push_back(y);
        a[x]={y,z};
    }
    sort(u.begin(),u.end());
    u.erase(unique(u.begin(),u.end()),u.end());
    for(i=1;i<=n;i++)
    {
        x=i;
        if(a[x].first==0)
            continue;
        a[x].first=lower_bound(u.begin(),u.end(),a[x].first)-u.begin()+1;
    }
    k=min(k,m);
    f(1,0);
    for(i=1;i<=k;i++)
    {
        s=max(s,dp[1][i]);
    }
    printf("%lld",s);
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%lld %lld %lld",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%lld",&x);
      |         ~~~~~^~~~~~~~~~~
magictree.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%lld %lld %lld",&x,&y,&z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31068 KB Output is correct
2 Correct 9 ms 31068 KB Output is correct
3 Correct 11 ms 31068 KB Output is correct
4 Correct 10 ms 31068 KB Output is correct
5 Correct 10 ms 31068 KB Output is correct
6 Correct 8 ms 31068 KB Output is correct
7 Correct 9 ms 31068 KB Output is correct
8 Correct 9 ms 31188 KB Output is correct
9 Correct 11 ms 31064 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 899400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 39512 KB Output is correct
2 Correct 14 ms 39516 KB Output is correct
3 Correct 13 ms 39516 KB Output is correct
4 Execution timed out 2059 ms 100716 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 899796 KB Output is correct
2 Correct 178 ms 899784 KB Output is correct
3 Correct 184 ms 902412 KB Output is correct
4 Correct 172 ms 901980 KB Output is correct
5 Correct 172 ms 906884 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31068 KB Output is correct
2 Correct 9 ms 31068 KB Output is correct
3 Correct 11 ms 31068 KB Output is correct
4 Correct 10 ms 31068 KB Output is correct
5 Correct 10 ms 31068 KB Output is correct
6 Correct 8 ms 31068 KB Output is correct
7 Correct 9 ms 31068 KB Output is correct
8 Correct 9 ms 31188 KB Output is correct
9 Correct 11 ms 31064 KB Output is correct
10 Correct 223 ms 899608 KB Output is correct
11 Correct 195 ms 899664 KB Output is correct
12 Correct 197 ms 902556 KB Output is correct
13 Correct 185 ms 901948 KB Output is correct
14 Correct 178 ms 906944 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 206556 KB Output is correct
2 Correct 449 ms 899572 KB Output is correct
3 Correct 471 ms 899564 KB Output is correct
4 Correct 523 ms 899588 KB Output is correct
5 Correct 1270 ms 901216 KB Output is correct
6 Correct 513 ms 901204 KB Output is correct
7 Correct 487 ms 902388 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31068 KB Output is correct
2 Correct 9 ms 31068 KB Output is correct
3 Correct 11 ms 31068 KB Output is correct
4 Correct 10 ms 31068 KB Output is correct
5 Correct 10 ms 31068 KB Output is correct
6 Correct 8 ms 31068 KB Output is correct
7 Correct 9 ms 31068 KB Output is correct
8 Correct 9 ms 31188 KB Output is correct
9 Correct 11 ms 31064 KB Output is correct
10 Correct 13 ms 39512 KB Output is correct
11 Correct 14 ms 39516 KB Output is correct
12 Correct 13 ms 39516 KB Output is correct
13 Execution timed out 2059 ms 100716 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31068 KB Output is correct
2 Correct 9 ms 31068 KB Output is correct
3 Correct 11 ms 31068 KB Output is correct
4 Correct 10 ms 31068 KB Output is correct
5 Correct 10 ms 31068 KB Output is correct
6 Correct 8 ms 31068 KB Output is correct
7 Correct 9 ms 31068 KB Output is correct
8 Correct 9 ms 31188 KB Output is correct
9 Correct 11 ms 31064 KB Output is correct
10 Execution timed out 2036 ms 899400 KB Time limit exceeded
11 Halted 0 ms 0 KB -