제출 #1099427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1099427		8pete8	Jobs (BOI24_jobs)	C++17	54 / 100	2033 ms	33104 KiB

Main

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
//#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
#define double long double
using namespace std;
const int mod=998244353,mxn=3e5+5,inf=1e18,minf=-1e18,lg=62;
int p[mxn+10],val[mxn+10];
vector<int>adj[mxn+10];
int del[mxn+10],profit[mxn+10];
int mnsum[mxn+10],dp[mxn+10];
int ans=0,ans2=0,n,k;
int pa[mxn+10];
int find(int u){return pa[u]==u?u:pa[u]=find(pa[u]);}
void merg(int a,int b){
    a=find(a),b=find(b);
    if(a==b)return;
    pa[b]=a;
}
vector<int>have;
void dfs(int cur){
    profit[cur]+=val[cur];
    if(-profit[cur]>ans+k)return;
    have.pb(cur);
    for(auto i:adj[cur]){
        profit[i]=profit[cur];
        dfs(i);
        if(dp[i]>0)dp[cur]+=dp[i],merg(cur,i);
    }
    dp[cur]=max(0LL,dp[cur]+val[cur]);
}
void dfs2(int cur){
    for(auto i:adj[cur]){
        dfs2(i);
        dp[cur]+=max(0LL,dp[i]);
    }
    dp[cur]=max(0LL,dp[cur]+val[cur]);
}
int32_t main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>val[i]>>p[i];
        adj[p[i]].pb(i);
    }
    if(k==inf){
        for(int i=1;i<=n;i++)if(!p[i])dfs2(i),ans2+=dp[i];
        cout<<ans2<<'\n';
        return 0;
    }
    for(int i=1;i<=n;i++){
        for(int i=1;i<=n;i++)profit[i]=0,dp[i]=0,pa[i]=i;
        for(int i=1;i<=n;i++)if(!p[i]){
            have.clear();
            dfs(i);
            if(dp[i]==0)continue;
            for(auto j:have)if(!del[j]&&find(j)==find(i)){
                while(p[j]){
                    if(del[j])break;
                    ans+=val[j];
                    val[j]=0;
                    del[j]=1;
                    j=p[j];
                }
                ans+=val[j];
                val[j]=0;
                del[j]=1;
            }
        }
    }
    cout<<ans<<"\n";
}
/*
7 -1
-6 0
-7 1
3 0
7 0
-1 0
4 5
-3 6
 
6 1 
3 0 
-3 1 
-5 0 
2 1 
6 3 
-4 5
 
1000000000000000000
14 5
2 3
3 1
4 2
5 3
6 3
2 1
-3 0
2 7
-3 7
-1 8
2 8
5 9
2 9
2 10
 
5 4
-4 0
1 1
1 1
1 1
2 1
*/

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

Main.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
Main.cpp:43:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   43 | int find(int u){return pa[u]==u?u:pa[u]=find(pa[u]);}
      |               ^
Main.cpp:44:22: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   44 | void merg(int a,int b){
      |                      ^
Main.cpp:50:17: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   50 | void dfs(int cur){
      |                 ^
Main.cpp:61:18: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   61 | void dfs2(int cur){
      |                  ^
Main.cpp:68:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   68 | int32_t main(){
      |              ^

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 29 / 29
• Subtask 5: 0 / 31