QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #669314 | #8232. Yet Another Shortest Path Query | qzez | Compile Error | / | / | C++14 | 1.8kb | 2024-10-23 18:07:55 | 2024-10-23 18:07:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+10,INF=1e9;
int n,m,q;
vector<tuple<int,int,int>>E;
mt19937 rnd(time(0));
vector<tuple<int,int,int>>Q;
int p[N];
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
struct edges{
int to,w,nex;
}edge[N*2];
int kk,head[N];
void add(int u,int v,int w){
edge[++kk]={v,w,head[u]},head[u]=kk;
}
int vis[N],fa[N];
ll dis[N];
void dfs(int u,int fa=0){
vis[u]=1;
::fa[u]=fa;
for(int i=head[u];i;i=edge[i].nex){
int v=edge[i].to;
if(v==fa)continue;
dis[v]=dis[u]+edge[i].w;
dfs(v,u);
}
}
void run(){
shuffle(E.begin(),E.end(),rnd);
iota(p,p+1+n,0);
kk=0,fill(head,head+1+n,0);
for(auto [u,v,w]:E){
int x=find(u),y=find(v);
if(x==y)continue;
add(u,v,w),add(v,u,w);
p[x]=y;
}
fill(vis,vis+1+n,0);
for(int i=1;i<=n;i++)if(!vis[i])dis[i]=0,dfs(i);
for(auto &[u,v,ans]:Q){
if(dis[u]>dis[v])swap(u,v);
if(fa[v]==u)ans=min(ans,dis[v]-dis[u]);
else if(fa[v]==fa[u]&&fa[u])ans=min(ans,dis[u]+dis[v]-dis[fa[u]]*2);
else if(fa[fa[v]]==u)ans=min(ans,dis[v]-dis[u]);
else if(fa[fa[fa[v]]]==u)ans=min(ans,dis[v]-dis[u]);
else if(fa[fa[v]]==fa[u]&&fa[u])ans=min(ans,dis[v]+dis[u]-dis[fa[u]]*2);
else if(fa[v]&&fa[v]==fa[fa[u]])ans=min(ans,dis[v]+dis[u]-dis[fa[v]]*2);
}
}
int main(){
scanf("%d%d",&n,&m);
E.resize(m);
for(auto &[u,v,w]:E){
scanf("%d%d%d",&u,&v,&w);
}
scanf("%d",&q);
Q.resize(q);
for(auto &[u,v,ans]:Q){
scanf("%d%d",&u,&v);
ans=INF;
}
for(;;){
run();
if(1.0*clock()/CLOCKS_PER_SEC>11.5)break;
}
for(auto [u,v,ans]:Q)printf("%d\n",ans<INF?ans:-1);
return 0;
}
Details
answer.code: In function ‘void run()’:
answer.code:36:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
36 | for(auto [u,v,w]:E){
| ^
answer.code:44:15: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
44 | for(auto &[u,v,ans]:Q){
| ^
answer.code:46:28: error: no matching function for call to ‘min(std::tuple_element<2, std::tuple<int, int, int> >::type&, ll)’
46 | if(fa[v]==u)ans=min(ans,dis[v]-dis[u]);
| ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from answer.code:1:
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)’
233 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: template argument deduction/substitution failed:
answer.code:46:28: note: deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘ll’ {aka ‘long long int’})
46 | if(fa[v]==u)ans=min(ans,dis[v]-dis[u]);
| ~~~^~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)’
281 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: template argument deduction/substitution failed:
answer.code:46:28: note: deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘ll’ {aka ‘long long int’})
46 | if(fa[v]==u)ans=min(ans,dis[v]-dis[u]);
| ~~~^~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)’
5775 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: template argument deduction/substitution failed:
answer.code:46:28: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
46 | if(fa[v]==u)ans=min(ans,dis[v]-dis[u]);
| ~~~^~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)’
5785 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: template argument deduction/substitution failed:
answer.code:46:28: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
46 | if(fa[v]==u)ans=min(ans,dis[v]-dis[u]);
| ~~~^~~~~~~~~~~~~~~~~~~
answer.code:47:44: error: no matching function for call to ‘min(std::tuple_element<2, std::tuple<int, int, int> >::type&, ll)’
47 | else if(fa[v]==fa[u]&&fa[u])ans=min(ans,dis[u]+dis[v]-dis[fa[u]]*2);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)’
233 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: template argument deduction/substitution failed:
answer.code:47:44: note: deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘ll’ {aka ‘long long int’})
47 | else if(fa[v]==fa[u]&&fa[u])ans=min(ans,dis[u]+dis[v]-dis[fa[u]]*2);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)’
281 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: template argument deduction/substitution failed:
answer.code:47:44: note: deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘ll’ {aka ‘long long int’})
47 | else if(fa[v]==fa[u]&&fa[u])ans=min(ans,dis[u]+dis[v]-dis[fa[u]]*2);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)’
5775 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: template argument deduction/substitution failed:
answer.code:47:44: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
47 | else if(fa[v]==fa[u]&&fa[u])ans=min(ans,dis[u]+dis[v]-dis[fa[u]]*2);
| ...