제출 #1213664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213664		boss_zz	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	1042 ms	589824 KiB

bitaro

#include<bits/stdc++.h>
#define rep(a,b,c) for(ll a=b;a<=c;++a)
#define ll int
#define ff first
#define ss second
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll N=1e5+5,inf=1e18,B=300;
ll n,m,q,dp[N];
vector<ll> adj_pos[N],adj_opp[N],tmp;
vector<pll> T[N];
bitset<N> ban;
void F(vector<pll> &T){
    sort(T.begin(),T.end(),[](pll a,pll b){return a.ss>b.ss;});
    if((ll)T.size()>B) T.resize(B);
}
void build(){
    rep(i,1,n) T[i].push_back(mp(i,0));
    rep(i,2,n){
        for(ll j:adj_opp[i]) for(auto o:T[j]){
            T[i].push_back(mp(o.ff,o.ss+1));
            if((ll)T[i].size()>B*2) F(T[i]);
        }
        F(T[i]);
    }
}
ll SMALL(ll v){
    for(auto o:T[v]) if(!ban[o.ff]) return o.ss;
    return -1;
}
ll BIG(ll v){
    fill(dp+1,dp+n+1,-1);
    dp[v]=0;
    for(ll i=v-1;i>=1;--i){
        for(ll j:adj_pos[i]){
            if(dp[j]==-1) continue;
            dp[i]=max(dp[i],dp[j]+1);
        }
    }
    ll ans=-1;
    rep(i,1,v) if(!ban[i]) ans=max(ans,dp[i]);
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>q;
    rep(i,1,m){
        ll u,v;
        cin>>u>>v;
        if(u>v) swap(u,v);
        adj_pos[u].push_back(v);
        adj_opp[v].push_back(u);
    }
    build();
    while(q--){
        ll v,k,x;
        cin>>v>>k;
        rep(i,1,k) cin>>x,tmp.push_back(x),ban[x]=1;
        if(k>=B) cout<<BIG(v)<<'\n';
        else cout<<SMALL(v)<<'\n';
        for(ll i:tmp) ban[i]=0;
        vector<ll>().swap(tmp);
    }
    return 0;
}

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

bitaro.cpp:10:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   10 | const ll N=1e5+5,inf=1e18,B=300;
      |                      ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86