Submission #172721

#	Time	Username	Problem	Language	Result	Execution time	Memory
172721		Ruxandra985	Fireworks (APIO16_fireworks)	C++14	0 / 100	15 ms	7544 KiB

fireworks

#include <bits/stdc++.h>
#define DIMN 300010
using namespace std;
vector <pair <int,int> > v[DIMN];
pair <int,int> sol[DIMN];
int sum[DIMN] , n , m;
int modul (int x){
    if (x > 0)
        return x;
    return -x;
}
void dfs (int nod){
    int i , vecin , s , val1 , val2;
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i].first;
        sum[nod] += v[nod][i].second;
        dfs(vecin);
    }

    if (nod > n){ /// e exploziv
        sol[nod] = make_pair(0 , sum[nod]); /// 0 e timpul si sum[nod] e costul
    }
    else { /// e doar punct de intersectie
        s = 0;
        for (i=0;i<v[nod].size();i++){
            vecin = v[nod][i].first;
            s += v[nod][i].second + sol[vecin].first;
        }
        /// vezi daca e mai ok s sau s + 1
        s/=v[nod].size();
        val1 = val2 = 0;
        for (i=0;i<v[nod].size();i++){
            vecin = v[nod][i].first;
            val1 += sol[vecin].second + modul (s - sol[vecin].first - v[nod][i].second);
            val2 += sol[vecin].second + modul (s+1 - sol[vecin].first - v[nod][i].second);
        }

        if (val1 <= val2){
            sol[nod] = make_pair(s , val1);
        }
        else sol[nod] = make_pair(s+1 , val2);
    }

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int tot , i , x , y;
    fscanf (fin,"%d%d",&n,&m);
    tot = n + m;
    for (i=2;i<=tot;i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(make_pair(i,y));
    }
    dfs(1);
    fprintf (fout,"%d",sol[1].second);
    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(int)':
fireworks.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
fireworks.cpp:25:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
fireworks.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:50:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
fireworks.cpp:53:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~

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