oj.uz

Submission #946331

# Submission time Handle Problem Language Result Execution time Memory
946331 2024-03-14T13:54:06 Z vivkostov Fireworks (APIO16_fireworks) C++14
0 / 100
 3 ms 2652 KB 
#include<bits/stdc++.h>
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
struct cell
{
    long long int a,b;
    void read()
    {
        cin>>a>>b;
    }
};
long long int n,m,dp[2005][1005],base[2005];
cell a[2005];
vector<cell>v[3005];
void dfs(long long int beg,long long int par,long long int cen)
{
    long long int w;
    base[beg]=cen;
    for(long long int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i].a;
        if(w!=par)dfs(w,beg,cen+v[beg][i].b);
    }
}
void make_dp(long long int beg,long long int par,long long int cen)
{
    long long int w;
    if(v[beg].size()==1&&beg!=1)
    {
        for(long long int i=base[beg]-cen;i<=300;i++)
        {
            dp[beg][i]=abs(base[beg]-i);
        }
        return;
    }
    for(long long int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i].a;
        if(w!=par)make_dp(w,beg,v[beg][i].b);
    }
    if(v[beg].size()!=1||beg==1)
    {
        for(long long int i=base[beg]-cen;i<=300;i++)
        {
            dp[beg][i]=1000000000;
            for(long long int j=base[beg];j<=300;j++)
            {
                long long int seg=0;
                for(long long int z=0;z<v[beg].size();z++)
                {
                    w=v[beg][z].a;
                    seg+=dp[w][j];
                }
                seg+=abs(j-i);
                dp[beg][i]=min(dp[beg][i],seg);
            }
        }
        for(long long int i=0;i<base[beg]-cen;i++)
        {
            dp[beg][i]=-1;
        }
    }
}
void read()
{
    cin>>n>>m;
    for(long long int i=2;i<=n+m;i++)
    {
        a[i].read();
        v[i].push_back(a[i]);
        long long int g=a[i].a;
        a[i].a=i;
        v[g].push_back(a[i]);
    }
    dfs(1,0,0);
    make_dp(1,0,0);
    long long int otg=1000000000;
    for(long long int i=0;i<=300;i++)
    {
        otg=min(otg,dp[1][i]);
    }
    /*for(long long int i=9;i<=15;i++)
    {
        cout<<dp[3][i]<<" ";
    }
    cout<<endl;
    */
    cout<<otg<<endl;
}
int main()
{
    speed();
    read();
    return 0;
}

Compilation message

fireworks.cpp: In function 'void dfs(long long int, long long int, long long int)':
fireworks.cpp:24:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(long long int i=0;i<v[beg].size();i++)
      |                           ~^~~~~~~~~~~~~~
fireworks.cpp: In function 'void make_dp(long long int, long long int, long long int)':
fireworks.cpp:41:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(long long int i=0;i<v[beg].size();i++)
      |                           ~^~~~~~~~~~~~~~
fireworks.cpp:54:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |                 for(long long int z=0;z<v[beg].size();z++)
      |                                       ~^~~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Incorrect 3 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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