Submission #172730

#	Time	Username	Problem	Language	Result	Execution time	Memory
172730		Ruxandra985	Fireworks (APIO16_fireworks)	C++14	7 / 100	9 ms	7416 KiB

fireworks

#include <bits/stdc++.h>
#define DIMN 300010
using namespace std;
vector <pair <long long,long long> > v[DIMN];
pair <long long,long long> sol[DIMN];
long long sum[DIMN] , n , m;
long long modul (long long x){
    if (x > 0)
        return x;
    return -x;
}
FILE *fin = stdin;
FILE *fout = stdout;
long long check (long long x , long long nod){
    long long i , vecin , val=0;
    val = 0;
    for (i=0;i<v[nod].size();i++){
        vecin = v[nod][i].first;
        val += sol[vecin].second + modul (x - sol[vecin].first - v[nod][i].second);
    }
    return val;
}
void dfs (long long nod){
    long long i , vecin , s , val , st , dr , mid , op , x, y;
    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;
        }
        /// fa cautare ternara
        st = 0;
        dr = 1000000000000000000;
        op = 0;
        while (op<=100){
            mid = (st + dr)/2;
            x = check(mid-1 , nod);
            y = check(mid , nod);
            if (x < y)
                dr = mid;
            else st = mid;
            op++;
        }
        mid = (st + dr)/2;
        sol[nod] = make_pair(mid , check(mid , nod));
    }

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

Compilation message (stderr)

fireworks.cpp: In function 'long long int check(long long int, long long int)':
fireworks.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
fireworks.cpp: In function 'void dfs(long long int)':
fireworks.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
fireworks.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
fireworks.cpp:24:31: warning: unused variable 'val' [-Wunused-variable]
     long long i , vecin , s , val , st , dr , mid , op , x, y;
                               ^~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:61:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%lld%lld",&n,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
fireworks.cpp:64:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld%lld",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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