QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #352319 | #7991. 最小环 | Kevin5307 | Compile Error | / | / | C++20 | 3.1kb | 2024-03-13 09:21:20 | 2024-03-13 09:21:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;
set<int> G[400400];
ll f[400400],g[400400];
int u[400400],v[400400],tot;
map<int,int> E[400400];
int ind[300300];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(f,0x3f,sizeof(f));
memset(g,0x3f,sizeof(g));
int n,m;
cin>>n>>m;
ll ans=0x3f3f3f3f3f3f3f3f;
while(m--)
{
int u,v;
ll w;
cin>>u>>v>>w;
if(u==v)
{
ans=min(ans,w);
continue;
}
if(E[u].count(v))
{
int e=E[u][v];
if(::u[e]==u)
f[e]=min(f[e],w);
else
g[e]=min(g[e],w);
G[u].insert(e);
G[v].insert(e);
}
else
{
int e=++tot;
f[e]=w;
::u[e]=u;
::v[e]=v;
E[u][v]=E[v][u]=e;
G[u].insert(e);
G[v].insert(e);
}
}
queue<int> q;
for(int i=1;i<=n;i++)
if(G[i].size()<=2)
q.push(i);
while(!q.empty())
{
int x=q.front();
q.pop();
if(!G[x].size()) break;
if(G[x].size()==1)
{
int e=*G[x].begin();
int y=u[e]+v[e]-x;
G[x].clear();
G[y].erase(e);
if(G[y].size()==2)
q.push(y);
}
else
{
int e1=*G[x].begin();
G[x].erase(e1);
int e2=*G[x].begin();
G[x].erase(e2);
int y1=u[e1]+v[e1]-x;
int y2=u[e2]+v[e2]-x;
G[y2].erase(e2);
if(u[e1]!=y1)
{
swap(u[e1],v[e1]);
swap(f[e1],g[e1]);
}
if(u[e2]!=x)
{
swap(u[e2],v[e2]);
swap(f[e2],g[e2]);
}
f[e1]+=f[e2];
g[e2]+=g[e2];
f[e1]=min(f[e1],0x3f3f3f3f3f3f3f3f);
g[e1]=min(g[e1],0x3f3f3f3f3f3f3f3f);
G[y2].insert(e1);
v[e1]=y2;
}
}
vector<int> vertex,edge;
for(int i=1;i<=n;i++)
if(G[i].size())
vertex.push_back(i);
for(auto x:vertex)
for(auto e:G[x])
if(x==u[e])
edge.push_back(e);
for(int i=0;i<vertex.size();i++)
ind[vertex[i]]=i+1;
for(auto ban:edge)
{
static ll dist[3030];
memset(dist,0x3f,sizeof(dist));
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
dist[ind[v[ban]]]=0;
pq.emplace(0,v[ban]);
while(!pq.empty())
{
int x=pq.top().second;
ll d=pq.top().first;
pq.pop();
if(dist[ind[x]]!=d)
continue;
for(auto e:G[x])
{
int y=u[e]+v[e]-x;
ll nd=d+(u[e]==x?f[e]:g[e]);
if(nd<dist[ind[y]])
{
dist[ind[y]]=nd;
pq.emplace(nd,y);
}
}
}
ans=min(ans,f[ban]+dist[ind[u[ban]]]);
}
for(auto e:edge)
swap(f[e],g[e]);
for(auto ban:edge)
{
static ll dist[3030];
memset(dist,0x3f,sizeof(dist));
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
dist[ind[v[ban]]]=0;
pq.emplace(0,v[ban]);
while(!pq.empty())
{
int x=pq.top().second;
ll d=pq.top().first;
pq.pop();
if(dist[ind[x]]!=d)
continue;
for(auto e:G[x])
{
int y=u[e]+v[e]-x;
ll nd=d+(u[e]==x?f[e]:g[e]);
if(nd<dist[ind[y]])
{
dist[ind[y]]=nd;
pq.emplace(nd,y);
}
}
}
ans=min(ans,f[ban]+dist[ind[u[ban]]]);
}
if(ans==0x3f3f3f3f3f3f3f3f)
{
cout<<"-1\n";
return 0;
}
cout<<ans<<endl;
return 0;
}
Details
answer.code: In function ‘int main()’:
answer.code:90:34: error: no matching function for call to ‘min(ll&, long int)’
90 | f[e1]=min(f[e1],0x3f3f3f3f3f3f3f3f);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
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:90:34: note: deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘long int’)
90 | f[e1]=min(f[e1],0x3f3f3f3f3f3f3f3f);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
/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:90:34: note: deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘long int’)
90 | f[e1]=min(f[e1],0x3f3f3f3f3f3f3f3f);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
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:90:34: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
90 | f[e1]=min(f[e1],0x3f3f3f3f3f3f3f3f);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
/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:90:34: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
90 | f[e1]=min(f[e1],0x3f3f3f3f3f3f3f3f);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:91:34: error: no matching function for call to ‘min(ll&, long int)’
91 | g[e1]=min(g[e1],0x3f3f3f3f3f3f3f3f);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
/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:91:34: note: deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘long int’)
91 | g[e1]=min(g[e1],0x3f3f3f3f3f3f3f3f);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
/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:91:34: note: deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘long int’)
91 | g[e1]=min(g[e1],0x3f3f3f3f3f3f3f3f);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
/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:91:34: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
91 | g[e1]=min(g[e1],0x3f3f3f3f3f3f3f3f);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
/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:91:34: note: mismatched types ‘std::initi...