Submission #39618

#	Time	Username	Problem	Language	Result	Execution time	Memory
39618		tada3k	Fireworks (APIO16_fireworks)	C++14	0 / 100	1619 ms	103936 KiB

fireworks

#include <bits/stdc++.h>
#define fi first
#define sd second
#define mp make_pair

using namespace std;

const int maxn = 5100;
const int oo = (int)1e9;

int n,m,f[maxn][maxn],c[maxn],p[maxn],res;
vector<pair<int, int> > g[maxn];

void visit(int u,int pa) {
    for (int j=0;j<g[u].size();j++) {
        int v = g[u][j].fi, c = g[u][j].sd;
        if (v!=pa) visit(v,u);
    }
    for (int X=0;X<=5000;X++) {
        for (int j=0;j<g[u].size();j++) {
            int v = g[u][j].fi, c = g[u][j].sd;
            if (v!=pa) {
                int temp=oo;
                for (int Y=0;Y<=X;Y++) temp = min(temp,f[v][Y] + abs(X-Y-c));
                f[u][X]+=temp;
            }
        }
    }
  // cout<<u<<endl;
   // for (int X=0;X<=20;X++) cout<<f[u][X]<<" ";
   // cout<<endl;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
   // freopen("in.txt","r",stdin);
    cin>>n>>m;
    for (int i=2;i<=n+m;i++) {
        cin>>p[i]>>c[i];
        g[i].push_back(mp(p[i],c[i]));
        g[p[i]].push_back(mp(i,c[i]));
    }
    for (int i=n+1;i<=n+m;i++)
        for (int Y=1;Y<=5000;Y++)
            f[i][Y]=oo;
    visit(1,-1);
    int temp=oo;
    for (int X=0;X<=5000;X++)
        if (temp > f[1][X] && f[1][X]!=0) {
            res = X;
            temp = f[1][X];
        }
    //cout<<res<<" "<<temp;
    cout<<temp;
}

Compilation message (stderr)

fireworks.cpp: In function 'void visit(int, int)':
fireworks.cpp:15:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j=0;j<g[u].size();j++) {
                   ^
fireworks.cpp:16:29: warning: unused variable 'c' [-Wunused-variable]
         int v = g[u][j].fi, c = g[u][j].sd;
                             ^
fireworks.cpp:20:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0;j<g[u].size();j++) {
                       ^

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