제출 #1280708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280708		StefanSebez	Fireworks (APIO16_fireworks)	C++20	26 / 100	52 ms	4008 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=5050;
const ll inf=1e16;
void chmn(ll &x,ll y){x=min(x,y);}
void chmx(ll &x,ll y){x=max(x,y);}
vector<pair<int,ll>>E[N];
ll Val[N],Val1[N];
int n,m;
void DFS1(int u){
    for(auto [i,w]:E[u]){
        Val1[i]=Val[i]=Val[u]+w;
        DFS1(i);
    }
}
struct SegTree{
    int root,nc,lc[2*N],rc[2*N];ll mn[2*N];
    SegTree(){mn[0]=inf;}
    void Update(int &c,int ss,int se,int qind,ll x){
        if(!c)c=++nc;
        if(ss==se){mn[c]=x;return;}
        int mid=ss+se>>1;
        if(qind<=mid) Update(lc[c],ss,mid,qind,x);
        else Update(rc[c],mid+1,se,qind,x);
        mn[c]=min(mn[lc[c]],mn[rc[c]]);
    }
    ll Get(int c,int ss,int se,int qs,int qe){
        if(qs>qe||qe<ss||se<qs)return inf;
        if(qs<=ss&&se<=qe)return mn[c];
        int mid=ss+se>>1;return min(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
    }
}ST[2];
ll dp[N][N];
void DFS(int u){
    if(E[u].empty()){
        for(int x=1;x<=n;x++) if(Val[x]!=Val1[u]) dp[u][x]=inf;
        return;
    }
    for(auto [c,w]:E[u]) DFS(c);
    for(auto [c,w]:E[u]){
        for(int y=1;y<=n;y++){
            ST[0].Update(ST[0].root,1,n,y,dp[c][y]-Val[y]);
            ST[1].Update(ST[1].root,1,n,y,dp[c][y]+Val[y]);
        }
        for(int x=1;x<=n;x++){
            ll mn=inf;
            int lb=upper_bound(Val+1,Val+n+1,Val[x])-Val-1;
            int ub=upper_bound(Val+1,Val+n+1,Val[x]+w)-Val-1;
            /*for(int i=1;i<=n;i++) printf("%lld ",Val[i]);printf("\n");
            printf("%lld: %i\n",Val[x],lb);
            printf("%lld: %i\n",Val[x]+w,ub);*/
            if(0<lb) chmn(mn,ST[0].Get(ST[0].root,1,n,1,lb)+Val[x]);
            if(lb<ub) chmn(mn,ST[1].Get(ST[1].root,1,n,lb+1,ub)-Val[x]);
            /*for(int y=1;y<=n;y++){
                if(Val[y]-w<=Val[x]) chmn(mn,dp[c][y]+abs(Val[x]-Val[y]));
            }*/
            dp[u][x]+=mn;
            chmn(dp[u][x],inf);
        }
    }
}
int main(){
    scanf("%i%i",&n,&m);n+=m;
    for(int i=2;i<=n;i++){
        int p;ll w;scanf("%i%lld",&p,&w);
        E[p].pb({i,w});
    }
    DFS1(1);
    sort(Val+1,Val+1+n);
    DFS(1);
    ll res=inf;
    for(int i=1;i<=n;i++) chmn(res,dp[1][i]);
    printf("%lld\n",res);
    return 0;
}

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

fireworks.cpp: In function 'int main()':
fireworks.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%i%i",&n,&m);n+=m;
      |     ~~~~~^~~~~~~~~~~~~~
fireworks.cpp:70:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         int p;ll w;scanf("%i%lld",&p,&w);
      |                    ~~~~~^~~~~~~~~~~~~~~~

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