社区讨论

求助大佬,有关变量大小

学术版参与者 4已保存回复 14

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
14 条
当前快照
1 份
快照标识符
@mi4reb1d
此快照首次捕获于
2025/11/18 23:59
3 个月前
此快照最后确认于
2025/11/20 04:26
3 个月前
查看原帖
求助大佬,改了2小时都没发现哪里爆int了
WA 20pts:
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pa pair<int,ll>
const int N=3e5+5,M=7e5+5,K=250005;
const ll inf=1e18;
int id,n,m,k,len,v[K],w[K],a,b,c,g[N],fir[N],bel[M],vis[M];
ll ans[N],sum[K],dis[M],d;
vector<pa>Q[N],s[M],t[M];
priority_queue<pa,vector<pa>,greater<pa>>q;
int main(){
    scanf("%d%d%d%d",&id,&n,&m,&k);
    for(int i=1;i<k;i++) scanf("%d",&v[i]);
    for(int i=2;i<=k;i++) scanf("%d",&w[i]),sum[i]=sum[i-1]+w[i];
    len=n;for(int i=1;i<=n;i++){
        scanf("%d",&g[i]);fir[i]=len;
        for(int j=1;j<=g[i];j++){
            bel[++len]=i;scanf("%d%d",&b,&c);Q[i].push_back({b,c});
            if(j<g[i]) s[len].push_back({len+1,v[j]});
            if(j>1) s[len].push_back({len-1,w[j]});
        }ans[i]=inf;bel[i]=i;
    }for(int i=1;i<=n;i++){
        k=0;for(pa j:Q[i]){
            t[fir[i]+(++k)].push_back({b=j.first,c=j.second});
            if(k<=g[b]) s[fir[i]+k].push_back({fir[b]+k,c});
            else if(g[b]) s[fir[i]+k].push_back({fir[b]+g[b],sum[k]-sum[g[b]]+c});
        }
    }for(int i=1;i<=len;i++) dis[i]=inf;
    if(g[1]) q.push({dis[n+1]=0,n+1});ans[1]=0;
    while(!q.empty()){
        a=q.top().second;q.pop();
        if(vis[a]++) continue;
        for(pa i:s[a]) if(dis[a]+(d=i.second)<dis[b=i.first]) q.push({dis[b]=dis[a]+d,b});
        for(pa i:t[a]) ans[bel[i.first]]=min(ans[bel[i.first]],dis[a]+i.second);
    }for(int i=1;i<=n;i++) printf("%lld ",(ans[i]==inf?-1ll:ans[i]));
return 0;}
AC:
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pa pair<ll,ll>
const ll N=3e5+5,M=7e5+5,K=250005;
const ll inf=1e18;
ll id,n,m,k,len,v[K],w[K],a,b,c,g[N],fir[N],bel[M],vis[M];
ll ans[N],sum[K],dis[M],d;
vector<pa>Q[N],s[M],t[M];
priority_queue<pa,vector<pa>,greater<pa>>q;
int main(){
    scanf("%lld%lld%lld%lld",&id,&n,&m,&k);
    for(ll i=1;i<k;i++) scanf("%lld",&v[i]);
    for(ll i=2;i<=k;i++) scanf("%lld",&w[i]),sum[i]=sum[i-1]+w[i];
    len=n;for(ll i=1;i<=n;i++){
        scanf("%lld",&g[i]);fir[i]=len;
        for(ll j=1;j<=g[i];j++){
            bel[++len]=i;scanf("%lld%lld",&b,&c);Q[i].push_back({b,c});
            if(j<g[i]) s[len].push_back({len+1,v[j]});
            if(j>1) s[len].push_back({len-1,w[j]});
        }ans[i]=inf;bel[i]=i;
    }for(ll i=1;i<=n;i++){
        k=0;for(pa j:Q[i]){
            t[fir[i]+(++k)].push_back({b=j.first,c=j.second});
            if(k<=g[b]) s[fir[i]+k].push_back({fir[b]+k,c});
            else if(g[b]) s[fir[i]+k].push_back({fir[b]+g[b],sum[k]-sum[g[b]]+c});
        }
    }for(ll i=1;i<=len;i++) dis[i]=inf;
    if(g[1]) q.push({dis[n+1]=0,n+1});ans[1]=0;
    while(!q.empty()){
        a=q.top().second;q.pop();
        if(vis[a]++) continue;
        for(pa i:s[a]) if(dis[a]+(d=i.second)<dis[b=i.first]) q.push({dis[b]=dis[a]+d,b});
        for(pa i:t[a]) ans[bel[i.first]]=min(ans[bel[i.first]],dis[a]+i.second);
    }for(ll i=1;i<=n;i++) printf("%lld ",(ans[i]==inf?-1ll:ans[i]));
return 0;}

P13271 [NOI2025] 机器人

对于所有测试数据,保证:
  • 1n,m3×1051 \leq n, m \leq 3 \times 10^51k2.5×1051 \leq k \leq 2.5 \times 10^5
  • 对于所有 1ik11 \leq i \leq k - 1,均有 0vi1090 \leq v_i \leq 10^9
  • 对于所有 2ik2 \leq i \leq k,均有 0wi1090 \leq w_i \leq 10^9
  • 对于所有 1in1 \leq i \leq n,均有 0dik0 \leq d_i \leq k,且 i=1ndi=m\sum_{i=1}^{n} d_i = m
  • 对于所有 1in1 \leq i \leq n1jdi1 \leq j \leq d_i,均有 1yi,jn1 \leq y_{i,j} \leq n1zi,j1091 \leq z_{i,j} \leq 10^9

回复

14 条回复,欢迎继续交流。

正在加载回复...