제출 #264146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
264146		seroh9171	Fireworks (APIO16_fireworks)	C++17	0 / 100	152 ms	209528 KiB

fireworks

#include <cstdio>
#include <vector>
#include <deque>
#include <algorithm>

long long N = 0, M = 0;

// 0 -> parent number, 1 -> edge's weight
long long              parent  [300005][2];
long long              leaf    [300005];
std::deque<long long>  child   [300005];
std::vector<long long> segtree [300005];

long long partial_solver(long long node, long long t, long long offset);
//
long long partial_solver_odd(long long node, long long t, long long offset) {
    long long original = parent[node][1];
    long long mid      = segtree[node][segtree[node].size() / 2] - offset;
    long long change   = t - mid;
    if(change + original < 0) change = -original;

//    printf("t: %lld, mid: %lld, node: %lld, change : %lld,\n\n\n", t, mid, node, change);

    long long sum = std::abs(change);
    for(long long i : child[node])
        sum += partial_solver(i, t - (original + change), offset + (original + change));
    return sum;
}
long long partial_solver_even(long long node, long long t, long long offset) {
    long long original = parent[node][1];
    long long mid1      = segtree[node][segtree[node].size() / 2 - 1] - offset;
    long long mid2      = segtree[node][segtree[node].size() / 2] - offset;
    long long change1   = t - mid2;
    long long change2   = t - mid1;
    long long change = 0;
    if(change2 < 0) {
        change = change2;
        if(change2 + original < 0)
            change = -original;
    }
    if(change1 <= 0 && change2 >= 0)
        change = 0;
    if(change1 > 0)
        change = change1;

//    printf("t: %lld, mid1: %lld, mid2: %lld, node: %lld, change1 : %lld,\nchange2 : %lld, change: %lld\n\n\n", t, mid1, mid2, node, change1, change2, change);

    long long sum = std::abs(change);
    for(long long i : child[node]) {
        sum += partial_solver(i, t - (original + change), offset + (original + change));
    }
    return sum;
}

long long partial_solver(long long node, long long t, long long offset) {
    if(child[node].empty()) {
//        printf(" hehe %lld\n", t);
        return std::abs(t - parent[node][1]);
    }
    if(segtree[node].size() % 2)
        return partial_solver_odd(node, t, offset);
    return partial_solver_even(node, t, offset);
}

long long partial_solver(long long t) {
    long long ans = 0;
    for(long long i : child[1])
        ans += partial_solver(i, t, 0);
    return ans;
}

long long solver() {

    long long first = 0, last = 1e2, min = 1e2;
    while(first + 2 < last) {
        long long mid1arg = (2 * first + last) / 3;
        long long mid2arg = (first + 2 * last) / 3;

//        printf("mid1arg %lld mid2arg %lld\n", mid1arg, mid2arg);

        long long mid1 = partial_solver(mid1arg);
        long long mid2 = partial_solver(mid2arg);

        if(mid1 <= mid2) last  = mid2arg;
        if(mid1 >= mid2) first = mid1arg;
    }

    for(long long i = first; i <= last; i++)
        if(partial_solver(min) > partial_solver(i))
            min = i;
    
    return partial_solver(min);
}

void construct() {
    for(long long i = N + 1; i <= N + M; i++) {
        auto get_cost = [&]() -> long long {
            long long node = i, sum = 0;
            while(node) {
                sum  = parent[node][1] + sum;
                node = parent[node][0];
            }
            return sum;
        };
        auto append  = [&](int cost_root_to_leaf) -> void {
            long long node = i;
            while(node) {
                segtree[node].push_back(cost_root_to_leaf);
                node = parent[node][0];
            }
        };
        append(get_cost());
    }
    for(long long i = 1; i <= N + M; i++)
        std::sort(segtree[i].begin(), segtree[i].end());
}

int main() {
    scanf("%lld%lld", &N, &M);

    for(long long i = 2; i <= N; i++) {
        long long i_parent = 0, i_weight = 0;
        scanf("%lld%lld", &i_parent, &i_weight);
        parent[i][0]     = i_parent;
        parent[i][1]     = i_weight;
        child [i_parent] . push_back(i);
    }

    for(long long i = N + 1; i <= N + M; i++) {
        long long i_parent = 0, i_weight = 0;
        scanf("%lld%lld", &i_parent, &i_weight);
        parent[i][0] = i_parent;
        parent[i][1] = i_weight;
        child [i_parent]    . push_back(i);
    }

    construct();

    printf("%lld", solver());
}

컴파일 시 표준 에러 (stderr) 메시지

fireworks.cpp: In function 'int main()':
fireworks.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  119 |     scanf("%lld%lld", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
fireworks.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |         scanf("%lld%lld", &i_parent, &i_weight);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fireworks.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  131 |         scanf("%lld%lld", &i_parent, &i_weight);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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