Submission #32226

#	Time	Username	Problem	Language	Result	Execution time	Memory
32226		dqhungdl	Fireworks (APIO16_fireworks)	C++14	26 / 100	59 ms	9660 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
int n,m,F[305][305];
bool Free[305][305];
vector<ii> g[300005];

bool cmp(ii x1,ii x2)
{
    return x1.second<x2.second;
}

void Sub1()
{
    sort(g[1].begin(),g[1].end(),cmp);
    int tmp=g[1][int(g[1].size())/2].second;
    int64_t res=0;
    for(int i=0;i<g[1].size();i++)
        res+=abs(g[1][i].second-tmp);
    cout<<res;
}

int DFS(int u,int len)
{
    if(u==3&&len==1)
        int h=0;
    if(Free[u][len]==true)
        return F[u][len];
    Free[u][len]=true;
    if(g[u].size()==0)
    {
        if(len==0)
            return F[u][len]=0;
        return F[u][len]=1e9;
    }
    F[u][len]=0;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i].first;
        int w=g[u][i].second;
        int sum=1e9;
        for(int len1=0;len1<=len;len1++)
            sum=min(sum,DFS(v,len-len1)+abs(w-len1));
        F[u][len]=min(F[u][len]+sum,int(1e9));
    }
    return F[u][len];
}

void Sub2()
{
    int res=1e9;
    for(int i=0;i<=300;i++)
        res=min(res,DFS(1,i));
    cout<<res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("FIREWORKS.INP","r",stdin);
    cin>>n>>m;
    int u,w;
    for(int i=2;i<=n+m;i++)
    {
        cin>>u>>w;
        g[u].push_back(ii(i,w));
    }
    if(n==1)
        Sub1();
    else
        Sub2();
}

Compilation message (stderr)

fireworks.cpp: In function 'void Sub1()':
fireworks.cpp:19:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[1].size();i++)
                  ^
fireworks.cpp: In function 'int DFS(int, int)':
fireworks.cpp:27:13: warning: unused variable 'h' [-Wunused-variable]
         int h=0;
             ^
fireworks.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[u].size();i++)
                  ^

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