oj.uz

Submission #498044

# Submission time Handle Problem Language Result Execution time Memory
498044 2021-12-24T10:02:54 Z andrei_boaca Magic Tree (CEOI19_magictree) C++17
80 / 100
 2000 ms 17988 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long ll;
ll n,m,k,par[100005],niv[100005],dp[100005][3],val[100005],day[100005],minim[100005];
vector<int> muchii[100005];
struct date
{
    ll nod,day,val;
} v[100005];
void dfscontrol(int nod)
{
    if(nod==1)
        niv[nod]=1;
    for(int i=0;i<muchii[nod].size();i++)
    {
        int fiu=muchii[nod][i];
        par[fiu]=nod;
        niv[fiu]=niv[nod]+1;
        dfscontrol(fiu);
    }
}
bool comp(date a, date b)
{
    if(a.day!=b.day)
        return a.day<b.day;
    if(niv[a.nod]!=niv[b.nod])
        return niv[a.nod]>niv[b.nod];
    return 0;
}
bool comp1(date a, date b)
{
    return a.nod>b.nod;
}
void solve3()
{
    sort(v+1,v+m+1,comp1);
    for(int i=1;i<=1e5;i++)
        minim[i]=1e9;
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        int val=v[i].day;
        int st=0;
        int dr=i-1;
        int best=0;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(minim[mij]<=val)
            {
                best=mij;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        ans=max(ans,best+1);
        minim[best+1]=min(minim[best+1],val*1LL);
    }
    cout<<ans<<'\n';
}
void dfs(int nod)
{
    for(int i=0;i<muchii[nod].size();i++)
    {
        int fiu=muchii[nod][i];
        dfs(fiu);
    }
    if(val[nod]!=0&&day[nod]!=0)
        for(int i=day[nod];i<=day[nod];i++)
            dp[nod][i]+=val[nod];
    for(int i=0;i<muchii[nod].size();i++)
    {
        int fiu=muchii[nod][i];
        for(int j=1;j<=k;j++)
            dp[nod][j]+=dp[fiu][j];
    }
    dp[nod][2]=max(dp[nod][1],dp[nod][2]);
}
void solve4()
{
    for(int i=1;i<=m;i++)
    {
        int nod=v[i].nod;
        day[nod]=v[i].day;
        val[nod]=v[i].val;
    }
    dfs(1);
    cout<<max(dp[1][1],dp[1][k])<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k;
    bool is3=1;
    for(int i=2;i<=n;i++)
    {
        int p;
        cin>>p;
        par[i]=p;
        if(par[i]!=i-1)
            is3=0;
        muchii[p].push_back(i);
    }
    for(int i=1;i<=m;i++)
        cin>>v[i].nod>>v[i].day>>v[i].val;
    dfscontrol(1);
    sort(v+1,v+m+1,comp);
    if(k<=2)
    {
        solve4();
        return 0;
    }
    if(is3)
    {
        solve3();
        return 0;
    }
    for(int i=1;i<=m;i++)
    {
        int nod=v[i].nod;
        ll x=v[i].val;
        dp[nod][1]=dp[nod][0]+x;
        while(nod!=1)
        {
            nod=par[nod];
            dp[nod][0]+=x;
            if(dp[nod][0]-x<=dp[nod][1]&&dp[nod][0]>dp[nod][1])
                x=dp[nod][0]-dp[nod][1];
            else if(dp[nod][0]<=dp[nod][1])
            {
                x=0;
                break;
            }
        }
    }
    cout<<dp[1][0];
    return 0;
}

Compilation message

magictree.cpp: In function 'void dfscontrol(int)':
magictree.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=0;i<muchii[nod].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~
magictree.cpp: In function 'void dfs(int)':
magictree.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0;i<muchii[nod].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~
magictree.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i=0;i<muchii[nod].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8548 KB Output is correct
2 Correct 1844 ms 10588 KB Output is correct
3 Correct 59 ms 9364 KB Output is correct
4 Correct 45 ms 9092 KB Output is correct
5 Execution timed out 2082 ms 9668 KB Time limit exceeded

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3532 KB Output is correct
2 Correct 2 ms 3532 KB Output is correct
3 Correct 2 ms 3532 KB Output is correct
4 Correct 66 ms 12984 KB Output is correct
5 Correct 48 ms 13080 KB Output is correct
6 Correct 69 ms 13044 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 11844 KB Output is correct
2 Correct 80 ms 11852 KB Output is correct
3 Correct 64 ms 14532 KB Output is correct
4 Correct 37 ms 10704 KB Output is correct
5 Correct 51 ms 17988 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Correct 2 ms 3404 KB Output is correct
8 Correct 1 ms 2636 KB Output is correct
9 Correct 1 ms 2700 KB Output is correct
10 Correct 59 ms 10260 KB Output is correct
11 Correct 57 ms 10280 KB Output is correct
12 Correct 1229 ms 12268 KB Output is correct
13 Correct 34 ms 9140 KB Output is correct
14 Correct 62 ms 12776 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3740 KB Output is correct
2 Correct 22 ms 7988 KB Output is correct
3 Correct 32 ms 7872 KB Output is correct
4 Correct 22 ms 8140 KB Output is correct
5 Correct 9 ms 6688 KB Output is correct
6 Correct 40 ms 8444 KB Output is correct
7 Correct 42 ms 10144 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Correct 2 ms 3404 KB Output is correct
8 Correct 1 ms 2636 KB Output is correct
9 Correct 1 ms 2700 KB Output is correct
10 Correct 3 ms 3532 KB Output is correct
11 Correct 2 ms 3532 KB Output is correct
12 Correct 2 ms 3532 KB Output is correct
13 Correct 66 ms 12984 KB Output is correct
14 Correct 48 ms 13080 KB Output is correct
15 Correct 69 ms 13044 KB Output is correct
16 Correct 59 ms 10260 KB Output is correct
17 Correct 57 ms 10280 KB Output is correct
18 Correct 1229 ms 12268 KB Output is correct
19 Correct 34 ms 9140 KB Output is correct
20 Correct 62 ms 12776 KB Output is correct
21 Correct 16 ms 4224 KB Output is correct
22 Correct 48 ms 9256 KB Output is correct
23 Correct 55 ms 9304 KB Output is correct
24 Correct 65 ms 10260 KB Output is correct
25 Correct 39 ms 9176 KB Output is correct
26 Correct 1343 ms 10564 KB Output is correct
27 Correct 940 ms 12276 KB Output is correct

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Correct 2 ms 3404 KB Output is correct
8 Correct 1 ms 2636 KB Output is correct
9 Correct 1 ms 2700 KB Output is correct
10 Correct 46 ms 8548 KB Output is correct
11 Correct 1844 ms 10588 KB Output is correct
12 Correct 59 ms 9364 KB Output is correct
13 Correct 45 ms 9092 KB Output is correct
14 Execution timed out 2082 ms 9668 KB Time limit exceeded