QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #259416 | #7790. 最短路求和 | zhouhuanyi | Compile Error | / | / | C++14 | 6.8kb | 2023-11-20 21:49:28 | 2023-11-20 21:49:28 |
Judging History
This is the latest submission verdict.
- [2023-11-20 21:49:28]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2023-11-20 21:49:28]
- Submitted
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<ctime>
#define N 200000
#define M 8000
using namespace std;
const int inf=(int)(1e9);
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
int num,data,snum;
};
struct node
{
int x,y;
bool operator < (const node &t)const
{
return x!=t.x?x<t.x:y<t.y;
}
};
node st[N+1];
struct rds
{
int num,data;
bool operator < (const rds &t)const
{
return data>t.data;
}
};
struct edt
{
long long d1,d2,data;
bool operator < (const edt &t)const
{
return data<t.data;
}
};
edt prs[N+1];
int n,m,lg[N+1],tfa[N+1],num[N+1],length,leng,smz[N+1],tong[N+1],fa[N+1],nt[N+1],nt2[N+1],rst[N+1],sz[N+1],szt[N+1],dque[N+1],top,dque2[N+1],top2;
long long depth[N+1],delta[N+1],delta2[N+1],ans,dis[M+1][M+1],W[N+1],wdelta[N+1];
bool used[N+1],vis[N+1],vst[N+1],dst[N+1],vist[N+1];
vector<reads>E[N+1];
vector<reads>ES[N+1];
vector<int>v[N+1];
vector<long long>cnt[N+1];
vector<long long>cnt2[N+1];
map<node,int>p;
void add(int x,int y,int z,int w)
{
E[x].push_back((reads){y,z,w}),E[y].push_back((reads){x,z,w});
return;
}
void add2(int x,int y,int z)
{
ES[x].push_back((reads){y,z}),ES[y].push_back((reads){x,z});
return;
}
void dfs(int x)
{
used[x]=1;
for (int i=0;i<E[x].size();++i)
if (!used[E[x][i].num])
depth[E[x][i].num]=depth[x]+E[x][i].data,fa[E[x][i].num]=x,vis[E[x][i].snum]=1,dfs(E[x][i].num);
return;
}
void dfs2(int x)
{
int cnt=0,y=0;
dst[x]=vst[x];
for (int i=0;i<E[x].size();++i)
if (fa[E[x][i].num]==x)
{
dfs2(E[x][i].num),dst[x]|=dst[E[x][i].num],cnt+=dst[E[x][i].num];
if (dst[E[x][i].num]) y=E[x][i].num;
}
if (cnt>=2) vst[x]=1;
else nt[x]=nt[y];
if (vst[x]) nt[x]=x;
return;
}
void dfs3(int x)
{
if (dst[x]) rst[x]=x;
if (vst[x]) nt2[x]=x;
for (int i=0;i<E[x].size();++i)
if (fa[E[x][i].num]==x)
{
if (dst[E[x][i].num]) nt2[E[x][i].num]=nt2[x];
rst[E[x][i].num]=rst[x],dfs3(E[x][i].num);
}
return;
}
void dijkstra(int x)
{
int top;
priority_queue<rds>q;
for (int i=1;i<=length;++i) dis[x][i]=inf,used[i]=0;
q.push((rds){x,0}),dis[x][x]=0;
while (!q.empty())
{
top=q.top().num,q.pop();
if (used[top]) continue;
used[top]=1;
for (int i=0;i<ES[top].size();++i)
if (dis[x][ES[top][i].num]>dis[x][top]+ES[top][i].data)
dis[x][ES[top][i].num]=dis[x][top]+ES[top][i].data,q.push((rds){ES[top][i].num,dis[x][ES[top][i].num]});
}
return;
}
bool cmp(int x,int y)
{
return W[x]<W[y];
}
void dfs4(int x)
{
dque[++top]=x,vist[x]=szt[x]=1;
for (int i=0;i<E[x].size();++i)
if (!vist[E[x][i].num]&&nt[x]==nt[E[x][i].num]&&nt2[x]==nt2[E[x][i].num])
tfa[E[x][i].num]=E[x][i].data,dfs4(E[x][i].num),szt[x]+=szt[E[x][i].num];
return;
}
bool cmp2(int x,int y)
{
return depth[x]<depth[y];
}
int main()
{
int x,y,z,ps,cnts;
long long d1,d2,d3,d4,ds,ds1,ds2,res;
bool op;
for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
n=read(),m=read();
for (int i=1;i<=m;++i) x=read(),y=read(),z=read(),add(x,y,z,i);
dfs(1);
for (int i=1;i<=n;++i)
for (int j=0;j<E[i].size();++j)
if (!vis[E[i][j].snum])
vst[i]=1;
dfs2(1),dfs3(1);
for (int i=1;i<=n;++i)
{
nt[i]=nt[rst[i]],nt2[i]=nt2[rst[i]];
if (nt[i]) delta[i]=depth[nt[i]]-depth[rst[i]]+depth[i]-depth[rst[i]];
if (nt2[i]) delta2[i]=depth[i]-depth[nt2[i]];
}
for (int i=1;i<=n;++i)
if (vst[i])
tong[++length]=i,num[i]=length;
for (int i=1;i<=n;++i)
for (int j=0;j<E[i].size();++j)
if (num[i]<num[E[i][j].num]&&!vis[E[i][j].snum])
add2(num[i],num[E[i][j].num],E[i][j].data);
for (int i=1;i<=length;++i)
if (num[nt2[fa[tong[i]]]])
add2(i,num[nt2[fa[tong[i]]]],depth[tong[i]]-depth[nt2[fa[tong[i]]]]);
for (int i=0;i<=length;++i) dis[0][i]=dis[i][0]=inf;
for (int i=1;i<=length;++i) dijkstra(i);
for (int i=1;i<=n;++i)
{
if (p.find((node){nt[i],nt2[i]})==p.end()) st[++leng]=(node){num[nt[i]],num[nt2[i]]},p[(node){nt[i],nt2[i]}]=leng;
v[p[(node){nt[i],nt2[i]}]].push_back(i);
}
for (int i=1;i<=n;++i) W[i]=delta[i]-delta2[i];
for (int i=1;i<=leng;++i)
{
sort(v[i].begin(),v[i].end(),cmp),cnt[i].resize(v[i].size()),cnt2[i].resize(v[i].size());
for (int j=0;j<v[i].size();++j) cnt[i][j]=(j?cnt[i][j-1]:0)+delta[v[i][j]];
for (int j=(int)(v[i].size())-1;j>=0;--j) cnt2[i][j]=(j+1!=v[i].size()?cnt2[i][j+1]:0)+delta2[v[i][j]];
}
for (int j=1;j<=leng;++j)
if (!v[j].empty())
{
for (int k=0;k<v[j].size();++k) wdelta[k]=W[v[j][k]];
for (int i=1;i<=j-1;++i)
if (!v[i].empty())
{
if (st[i].x==st[i].y&&st[j].x==st[j].y)
{
ans+=v[j].size()*cnt[i].back()+v[i].size()*cnt[j].back()+1ll*v[i].size()*v[j].size()*dis[st[i].x][st[j].x];
continue;
}
if (st[i].x==st[i].y)
{
for (int k=0;k<v[j].size();++k) ans+=v[i].size()*min(delta[v[j][k]]+dis[st[i].x][st[j].x],delta2[v[j][k]]+dis[st[i].x][st[j].y])+cnt[i].back();
continue;
}
if (st[j].x==st[j].y)
{
for (int k=0;k<v[i].size();++k) ans+=v[j].size()*min(delta[v[i][k]]+dis[st[j].x][st[i].x],delta2[v[i][k]]+dis[st[j].x][st[i].y])+cnt[j].back();
continue;
}
d1=dis[st[i].x][st[j].x],d2=dis[st[i].x][st[j].y],d3=dis[st[i].y][st[j].x],d4=dis[st[i].y][st[j].y];
for (int k=0;k<v[i].size();++k) ds1=min(delta[v[i][k]]+d1,delta2[v[i][k]]+d3),ds2=min(delta[v[i][k]]+d2,delta2[v[i][k]]+d4),prs[k]=(edt){ds1,ds2,ds2-ds1};
op=1;
for (int k=0;k+1<v[i].size();++k) op&=(v[i][k].data<=v[i][k+1].data);
if (!op) sort(prs,prs+v[i].size());
ps=-1;
for (int k=0;k<v[i].size();++k)
{
while (ps+1<v[j].size()&&wdelta[ps+1]<prs[k].data) ++ps;
if (ps!=-1) ans+=prs[k].d1*(ps+1)+cnt[j][ps];
if (ps+1!=v[j].size()) ans+=prs[k].d2*(v[j].size()-1-ps)+cnt2[j][ps+1];
}
}
}
for (int i=1;i<=n;++i) smz[rst[i]]++;
for (int i=1;i<=n;++i)
if (!vist[i])
{
if (!nt[i]||!nt2[i]||nt[i]==nt2[i])
{
top=0,dfs4(i);
for (int j=2;j<=top;++j) ans+=1ll*(szt[dque[1]]-szt[dque[j]])*szt[dque[j]]*tfa[dque[j]];
}
else
{
top=top2=ps=cnts=res=0,dfs4(i);
for (int j=2;j<=top;++j) ans+=1ll*(szt[dque[1]]-szt[dque[j]])*szt[dque[j]]*tfa[dque[j]];
for (int j=1;j<=top;++j)
if (dst[dque[j]])
dque2[++top2]=dque[j];
sort(dque2+1,dque2+top2+1,cmp2),ds=dis[num[nt[i]]][num[nt2[i]]]+depth[nt[i]]-depth[nt2[i]];
for (int j=1;j<=top2;++j)
{
while (ps+1<=j&&((depth[dque2[j]]-depth[dque2[ps+1]])<<1)>=ds) ++ps,cnts+=smz[dque2[ps]],res+=smz[dque2[ps]]*(depth[dque2[ps]]<<1);
ans-=(((depth[dque2[j]]<<1)-ds)*cnts-res)*smz[dque2[j]];
}
}
}
printf("%lld\n",ans);
return 0;
}
详细
answer.code: In function ‘void dijkstra(int)’:
answer.code:117:133: warning: narrowing conversion of ‘dis[x][ES[top].std::vector<reads>::operator[](((std::vector<reads>::size_type)i)).reads::num]’ from ‘long long int’ to ‘int’ [-Wnarrowing]
117 | dis[x][ES[top][i].num]=dis[x][top]+ES[top][i].data,q.push((rds){ES[top][i].num,dis[x][ES[top][i].num]});
| ~~~~~~~~~~~~~~~~~~~~~^
answer.code: In function ‘int main()’:
answer.code:206:88: error: request for member ‘data’ in ‘v[i].std::vector<int>::operator[](((std::vector<int>::size_type)k))’, which is of non-class type ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’}
206 | for (int k=0;k+1<v[i].size();++k) op&=(v[i][k].data<=v[i][k+1].data);
| ^~~~
answer.code:206:104: error: request for member ‘data’ in ‘v[i].std::vector<int>::operator[](((std::vector<int>::size_type)(k + 1)))’, which is of non-class type ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’}
206 | for (int k=0;k+1<v[i].size();++k) op&=(v[i][k].data<=v[i][k+1].data);
| ^~~~