oj.uz

Submission #39618

# Submission time Handle Problem Language Result Execution time Memory
39618 2018-01-16T18:48:26 Z tada3k Fireworks (APIO16_fireworks) C++14
0 / 100
 1619 ms 103936 KB 
#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

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.0

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

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 103936 KB Output is correct
2 Correct 646 ms 103936 KB Output is correct
3 Correct 1043 ms 103936 KB Output is correct
4 Incorrect 1619 ms 103936 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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