제출 #1356742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1356742		kokokai	Jobs (BOI24_jobs)	C++20	14 / 100	26 ms	14528 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define task "text"
#define int long long
const int N = 2e5+5;
vector<int> adj[N];
int p[N];
int x[N];
int n;
struct node{
    ll root,u,mnpre,pre;
    bool operator < (const node &oth) const{
        return mnpre < oth.mnpre;
    }
}dp[N];
void dfs(int u,int root,ll pre,ll mnpre){
    //if(u == 1 && root == 0) cerr<<mnpre<<'\n';
    mnpre=min(mnpre,pre);

    if(pre>0){
        if(mnpre > dp[root].mnpre){
            //if(root == 0) cerr<<mnpre<<'\n';
            dp[root]={root,u,mnpre,pre};
        }
    }
    for(int v:adj[u]){
        dfs(v,root,pre+x[v],mnpre);
    }
}
int vis[N];
signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
    }

    ll s;
    cin>>n>>s;
    //cerr<<n<<' '<<s<<'\n';
    for(int i=1;i<=n;i++){
        cin>>x[i]>>p[i];
        adj[p[i]].push_back(i);
    }
    for(int i=0;i<=n;i++){
        dp[i]={0,0,-(ll)2e18,0};
    }
    for(int i=0;i<=n;i++){
        dfs(i,i,x[i],x[i]);
    }
    priority_queue<node> pq;
    pq.push({dp[0]});
    ll ans=0;
    //cerr<<dp[4].mnpre<<'\n';
    while(!pq.empty()){

        ll sum=pq.top().pre;
        ll mnpre=pq.top().mnpre;
        ll u=pq.top().u;
        ll root=pq.top().root;
        pq.pop();
        if(s+mnpre >= 0){
            s += sum;
            ans += sum;
        }else break;
        //cerr<<u<<' '<<s<<'\n';
        int c=-1;
        while(!vis[u]){
            vis[u]=1;
            for(int v:adj[u]){
                if(v != c){
                    pq.push(dp[v]);
                }
            }
            c=u;
            u=p[u];
        }
    }
    cout<<ans<<'\n';
}

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

Main.cpp: In function 'int main()':
Main.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 서브태스크 1: 0 / 11
• 서브태스크 2: 14 / 14
• 서브태스크 3: 0 / 15
• 서브태스크 4: 0 / 29
• 서브태스크 5: 0 / 31