oj.uz

Submission #909204

# Submission time Handle Problem Language Result Execution time Memory
909204 2024-01-17T06:13:40 Z ibm2006 Magic Tree (CEOI19_magictree) C++17
34 / 100
 2000 ms 66740 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][22],h[1100000],m;
vector<ll> v[1100000];
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);
        a[x]={y,z};
    }
    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 9 ms 31068 KB Output is correct
2 Correct 10 ms 31068 KB Output is correct
3 Correct 10 ms 31068 KB Output is correct
4 Correct 9 ms 31068 KB Output is correct
5 Correct 9 ms 31236 KB Output is correct
6 Correct 9 ms 31068 KB Output is correct
7 Correct 8 ms 31068 KB Output is correct
8 Correct 10 ms 31428 KB Output is correct
9 Correct 8 ms 31068 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 56204 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 31320 KB Output is correct
2 Correct 13 ms 31324 KB Output is correct
3 Correct 14 ms 31580 KB Output is correct
4 Execution timed out 2068 ms 49852 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 56456 KB Output is correct
2 Correct 71 ms 57640 KB Output is correct
3 Correct 60 ms 61012 KB Output is correct
4 Correct 50 ms 57584 KB Output is correct
5 Correct 57 ms 66740 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31068 KB Output is correct
2 Correct 10 ms 31068 KB Output is correct
3 Correct 10 ms 31068 KB Output is correct
4 Correct 9 ms 31068 KB Output is correct
5 Correct 9 ms 31236 KB Output is correct
6 Correct 9 ms 31068 KB Output is correct
7 Correct 8 ms 31068 KB Output is correct
8 Correct 10 ms 31428 KB Output is correct
9 Correct 8 ms 31068 KB Output is correct
10 Correct 149 ms 56884 KB Output is correct
11 Correct 111 ms 56868 KB Output is correct
12 Correct 82 ms 60536 KB Output is correct
13 Correct 80 ms 56776 KB Output is correct
14 Correct 66 ms 65860 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31068 KB Output is correct
2 Correct 10 ms 31068 KB Output is correct
3 Correct 10 ms 31068 KB Output is correct
4 Correct 9 ms 31068 KB Output is correct
5 Correct 9 ms 31236 KB Output is correct
6 Correct 9 ms 31068 KB Output is correct
7 Correct 8 ms 31068 KB Output is correct
8 Correct 10 ms 31428 KB Output is correct
9 Correct 8 ms 31068 KB Output is correct
10 Correct 13 ms 31320 KB Output is correct
11 Correct 13 ms 31324 KB Output is correct
12 Correct 14 ms 31580 KB Output is correct
13 Execution timed out 2068 ms 49852 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

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