oj.uz

Submission #909280

# Submission time Handle Problem Language Result Execution time Memory
909280 2024-01-17T06:47:18 Z ibm2006 Magic Tree (CEOI19_magictree) C++17
71 / 100
 153 ms 65872 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],h[1100000],m;
vector<ll> v[1100000],u;
pair<ll,ll> a[1100000];
multiset<pair<ll,ll>> dp[110000];
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=0;i<h[x];i++)
    {
        if(v[x][i]==y)
            continue;
        if(dp[x].empty())
        {
            swap(dp[x],dp[v[x][i]]);
            continue;
        }
        if(dp[x].size()<dp[v[x][i]].size())
            swap(dp[x],dp[v[x][i]]);
        for(pair<ll,ll> p:dp[v[x][i]])
        {
            dp[x].insert(p);
        }
        dp[v[x][i]].clear();
    }
    if(a[x].first==0)
        return;
    dp[x].insert({a[x].first,a[x].second});
    pair<ll,ll> p;
    p={a[x].first+1,0};
    s=0;
    pair<ll,ll> id;
    while(1)
    {
        if(dp[x].lower_bound(p)==dp[x].end())
            break;
        id=(*dp[x].lower_bound(p));
        if(id.second+s>=a[x].second)
        {
            dp[x].erase(dp[x].find(id));
            dp[x].insert({id.first,id.second+s-a[x].second});
            break;
        }
        dp[x].erase(dp[x].find(id));
        s+=id.second;
    }
}
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(pair<ll,ll> p:dp[1])
    {
        s+=p.second;
    }
    printf("%lld",s);
}

Compilation message

magictree.cpp: In function 'void f(ll, ll)':
magictree.cpp:10:10: warning: unused variable 'j' [-Wunused-variable]
   10 |     ll i,j;
      |          ^
magictree.cpp: In function 'int main()':
magictree.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%lld %lld %lld",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%lld",&x);
      |         ~~~~~^~~~~~~~~~~
magictree.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%lld %lld %lld",&x,&y,&z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35420 KB Output is correct
2 Correct 9 ms 35292 KB Output is correct
3 Correct 10 ms 35416 KB Output is correct
4 Correct 10 ms 35504 KB Output is correct
5 Correct 10 ms 35496 KB Output is correct
6 Correct 10 ms 35416 KB Output is correct
7 Correct 9 ms 35420 KB Output is correct
8 Correct 10 ms 35276 KB Output is correct
9 Correct 9 ms 35484 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 43596 KB Output is correct
2 Correct 73 ms 50152 KB Output is correct
3 Correct 119 ms 48864 KB Output is correct
4 Correct 76 ms 47088 KB Output is correct
5 Correct 101 ms 49236 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 35672 KB Output is correct
2 Correct 12 ms 35676 KB Output is correct
3 Correct 11 ms 35676 KB Output is correct
4 Correct 81 ms 59672 KB Output is correct
5 Correct 98 ms 65872 KB Output is correct
6 Correct 115 ms 59476 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 ms 46672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35420 KB Output is correct
2 Correct 9 ms 35292 KB Output is correct
3 Correct 10 ms 35416 KB Output is correct
4 Correct 10 ms 35504 KB Output is correct
5 Correct 10 ms 35496 KB Output is correct
6 Correct 10 ms 35416 KB Output is correct
7 Correct 9 ms 35420 KB Output is correct
8 Correct 10 ms 35276 KB Output is correct
9 Correct 9 ms 35484 KB Output is correct
10 Correct 153 ms 46744 KB Output is correct
11 Correct 112 ms 47220 KB Output is correct
12 Correct 97 ms 50380 KB Output is correct
13 Correct 61 ms 47048 KB Output is correct
14 Correct 98 ms 59524 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 36184 KB Output is correct
2 Correct 41 ms 41300 KB Output is correct
3 Correct 48 ms 41344 KB Output is correct
4 Correct 61 ms 41328 KB Output is correct
5 Correct 26 ms 41424 KB Output is correct
6 Correct 47 ms 45196 KB Output is correct
7 Correct 43 ms 48472 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35420 KB Output is correct
2 Correct 9 ms 35292 KB Output is correct
3 Correct 10 ms 35416 KB Output is correct
4 Correct 10 ms 35504 KB Output is correct
5 Correct 10 ms 35496 KB Output is correct
6 Correct 10 ms 35416 KB Output is correct
7 Correct 9 ms 35420 KB Output is correct
8 Correct 10 ms 35276 KB Output is correct
9 Correct 9 ms 35484 KB Output is correct
10 Correct 11 ms 35672 KB Output is correct
11 Correct 12 ms 35676 KB Output is correct
12 Correct 11 ms 35676 KB Output is correct
13 Correct 81 ms 59672 KB Output is correct
14 Correct 98 ms 65872 KB Output is correct
15 Correct 115 ms 59476 KB Output is correct
16 Correct 153 ms 46744 KB Output is correct
17 Correct 112 ms 47220 KB Output is correct
18 Correct 97 ms 50380 KB Output is correct
19 Correct 61 ms 47048 KB Output is correct
20 Correct 98 ms 59524 KB Output is correct
21 Correct 27 ms 37720 KB Output is correct
22 Correct 93 ms 44672 KB Output is correct
23 Correct 94 ms 44464 KB Output is correct
24 Correct 122 ms 47560 KB Output is correct
25 Correct 70 ms 47044 KB Output is correct
26 Correct 123 ms 51540 KB Output is correct
27 Correct 122 ms 50996 KB Output is correct

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35420 KB Output is correct
2 Correct 9 ms 35292 KB Output is correct
3 Correct 10 ms 35416 KB Output is correct
4 Correct 10 ms 35504 KB Output is correct
5 Correct 10 ms 35496 KB Output is correct
6 Correct 10 ms 35416 KB Output is correct
7 Correct 9 ms 35420 KB Output is correct
8 Correct 10 ms 35276 KB Output is correct
9 Correct 9 ms 35484 KB Output is correct
10 Correct 76 ms 43596 KB Output is correct
11 Correct 73 ms 50152 KB Output is correct
12 Correct 119 ms 48864 KB Output is correct
13 Correct 76 ms 47088 KB Output is correct
14 Correct 101 ms 49236 KB Output is correct
15 Correct 11 ms 35672 KB Output is correct
16 Correct 12 ms 35676 KB Output is correct
17 Correct 11 ms 35676 KB Output is correct
18 Correct 81 ms 59672 KB Output is correct
19 Correct 98 ms 65872 KB Output is correct
20 Correct 115 ms 59476 KB Output is correct
21 Incorrect 149 ms 46672 KB Output isn't correct
22 Halted 0 ms 0 KB -