제출 #402591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
402591		qwerasdfzxcl	Fireworks (APIO16_fireworks)	C++14	7 / 100	6 ms	7372 KiB

fireworks

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<pair<int, int>> adj[300300];
pair<ll, ll> ran[300300];
priority_queue<ll> pq1;
priority_queue<ll, vector<ll>, greater<ll>> pq2;
ll dp[300300];

void ins(ll x, ll y){
    vector<ll> tmp;
    int c=0;
    while(!pq1.empty() && c<2){
        tmp.push_back(pq1.top());
        tmp.push_back(pq2.top());
        pq1.pop();pq2.pop();
        c++;
    }
    tmp.push_back(x);
    tmp.push_back(y);
    sort(tmp.begin(), tmp.end());
    for (int i=0;i<(int)tmp.size()/2;i++) pq1.push(tmp[i]);
    for (int i=(int)tmp.size()/2;i<(int)tmp.size();i++) pq2.push(tmp[i]);
}

ll calc(ll val, ll s, ll e){
    if (s<=val && val<=e) return 0;
    if (e<val) return val-e;
    return s-val;
}

void dfs(int s, ll cur){
    if (adj[s].empty()){
        ran[s] = {cur, cur}, dp[s] = 0;
        return;
    }
    for (auto &v:adj[s]) dfs(v.first, cur+v.second);
    for (auto &v:adj[s]) ins(ran[v.first].first, ran[v.first].second);
    ran[s] = {pq1.top(), pq2.top()};
    for (auto &v:adj[s]) dp[s] += calc(ran[s].first, ran[v.first].first, ran[v.first].second)+dp[v.first];
    while(!pq1.empty()) pq1.pop();
    while(!pq2.empty()) pq2.pop();
    //printf("%d: %lld %lld %lld\n", s, ran[s].first, ran[s].second, dp[s]);
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i=2;i<=n+m;i++){
        int p, c;
        scanf("%d %d", &p, &c);
        adj[p].push_back({i, c});
    }
    dfs(1, 0);
    printf("%lld\n", dp[1]);
    return 0;
}

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

fireworks.cpp: In function 'int main()':
fireworks.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
fireworks.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d %d", &p, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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