oj.uz

Submission #172730

# Submission time Handle Problem Language Result Execution time Memory
172730 2020-01-02T13:22:52 Z Ruxandra985 Fireworks (APIO16_fireworks) C++14
7 / 100
 9 ms 7416 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 9 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 9 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Incorrect 8 ms 7416 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 9 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Incorrect 8 ms 7416 KB Output isn't correct
12 Halted 0 ms 0 KB -