Submission #946289

#	Time	Username	Problem	Language	Result	Execution time	Memory
946289		vivkostov	Fireworks (APIO16_fireworks)	C++14	0 / 100	3 ms	604 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
struct cell
{
    int a,b;
    void read()
    {
        cin>>a>>b;
    }
};
int n,m,dp[2005][305],base[2005];
cell a[2005];
vector<cell>v[3005];
void dfs(int beg,int par,int cen)
{
    int w;
    base[beg]=cen;
    for(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(int beg,int par,int cen)
{
    int w;
    if(v[beg].size()==1&&beg!=1)
    {
        for(int i=base[beg]-cen;i<=300;i++)
        {
            dp[beg][i]=abs(base[beg]-i);
        }
        for(int i=0;i<base[beg]-cen;i++)
        {
            dp[beg][i]=-1;
        }
        return;
    }
    for(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(int i=base[beg]-cen;i<=300;i++)
        {
            dp[beg][i]=1000000;
            for(int j=base[beg];j<=300;j++)
            {
                int seg=0;
                for(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(int i=0;i<base[beg]-cen;i++)
        {
            dp[beg][i]=-1;
        }
    }
}
void read()
{
    cin>>n>>m;
    for(int i=2;i<=n+m;i++)
    {
        a[i].read();
        v[i].push_back(a[i]);
        int g=a[i].a;
        a[i].a=i;
        v[g].push_back(a[i]);
    }
    dfs(1,0,0);
    make_dp(1,0,0);
    int otg=100000000;
    for(int i=0;i<=300;i++)
    {
        otg=min(otg,dp[1][i]);
    }
    /*for(int i=9;i<=15;i++)
    {
        cout<<dp[3][i]<<" ";
    }
    cout<<endl;
    */
    cout<<otg<<endl;
}
int main()
{
    speed();
    read();
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45