| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 666854 | kirakaminski968 | Robot (JOI21_ho_t4) | C++17 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define setp() cout << setprecision(15)
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;
struct Edge{
int nxt,c;
ll e;
};
int n,m;
ll dist[N][2] ;
vector<Edge> g[N];
map<int,ll> s[N];
int t;
void solve(){
cin >> n >> m;
for(int i = 0;i<n;i++){
int u,v,c;
ll e;
cin >> u >> v >> c >> e;
g[u].push_back({v,c,e});
g[v].push_back({u,c,e});
s[u][c] += e;
s[v][c] += e;
}
for(int i = 1;i<=n;++i) dist[i][0] = dist[i][1] = 1e18;
priority_queue<array<ll,3>> pq(n);
vector<bool> vis[2];
vis[0].resize(n+1);
vis[1].resize(n+1);
dist[n][0] = 0;
pq.push(0,n,1);
while(pq.size()){
int v = pq.top()[1], cc = pq.top()[2];
ll D = -pq.top()[0];
pq.pop();
if(vis[cc == -1][v]) continue;
vis[cc == -1][v] = 1;
for(auto E : g[v]){
int c = E.c, nxt = E.nxt;
ll e = E.e, val = s[nxt][c];
if(cc == c) e = 0;
if(D + e < dist[nxt][0]){
dist[nxt][0] = D+e;
pq.push({-dist[nxt][0],nxt,-1});
}
if(D - e + val < dist[nxt][1]){
dist[nxt][1] = D-e+val;
pq.push({-dist[nxt][1],nxt,c});
}
}
}
if(min(dist[1][0],dist[1][1]) == 1e18) cout << -1;
else cout << min(dist[1][0],dist[1][1]);
}
int main(){
cin >> t;
while(t--){
solve();
cout << endl;
}
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'void solve()':
Main.cpp:32:35: error: no matching function for call to 'std::priority_queue<std::array<long long int, 3> >::priority_queue(int&)'
32 | priority_queue<array<ll,3>> pq(n);
| ^
In file included from /usr/include/c++/10/queue:64,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:597:2: note: candidate: 'template<class _InputIterator> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(_InputIterator, _InputIterator, const _Compare&, _Sequence&&) [with _InputIterator = _InputIterator; _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >; _Compare = std::less<std::array<long long int, 3> >]'
597 | priority_queue(_InputIterator __first, _InputIterator __last,
| ^~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:597:2: note: template argument deduction/substitution failed:
Main.cpp:32:35: note: candidate expects 4 arguments, 1 provided
32 | priority_queue<array<ll,3>> pq(n);
| ^
In file included from /usr/include/c++/10/queue:64,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:586:2: note: candidate: 'template<class _InputIterator> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(_InputIterator, _InputIterator, const _Compare&, const _Sequence&) [with _InputIterator = _InputIterator; _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >; _Compare = std::less<std::array<long long int, 3> >]'
586 | priority_queue(_InputIterator __first, _InputIterator __last,
| ^~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:586:2: note: template argument deduction/substitution failed:
Main.cpp:32:35: note: candidate expects 4 arguments, 1 provided
32 | priority_queue<array<ll,3>> pq(n);
| ^
In file included from /usr/include/c++/10/queue:64,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:554:2: note: candidate: 'template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(std::priority_queue<_Tp, _Sequence, _Compare>&&, const _Alloc&) [with _Alloc = _Alloc; _Requires = _Requires; _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >; _Compare = std::less<std::array<long long int, 3> >]'
554 | priority_queue(priority_queue&& __q, const _Alloc& __a)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:554:2: note: template argument deduction/substitution failed:
Main.cpp:32:35: note: candidate expects 2 arguments, 1 provided
32 | priority_queue<array<ll,3>> pq(n);
| ^
In file included from /usr/include/c++/10/queue:64,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:550:2: note: candidate: 'template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const std::priority_queue<_Tp, _Sequence, _Compare>&, const _Alloc&) [with _Alloc = _Alloc; _Requires = _Requires; _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >; _Compare = std::less<std::array<long long int, 3> >]'
550 | priority_queue(const priority_queue& __q, const _Alloc& __a)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:550:2: note: template argument deduction/substitution failed:
Main.cpp:32:35: note: candidate expects 2 arguments, 1 provided
32 | priority_queue<array<ll,3>> pq(n);
| ^
In file included from /usr/include/c++/10/queue:64,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:545:2: note: candidate: 'template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, _Sequence&&, const _Alloc&) [with _Alloc = _Alloc; _Requires = _Requires; _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >; _Compare = std::less<std::array<long long int, 3> >]'
545 | priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:545:2: note: template argument deduction/substitution failed:
Main.cpp:32:35: note: candidate expects 3 arguments, 1 provided
32 | priority_queue<array<ll,3>> pq(n);
| ^
In file included from /usr/include/c++/10/queue:64,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:539:2: note: candidate: 'template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, const _Sequence&, const _Alloc&) [with _Alloc = _Alloc; _Requires = _Requires; _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >; _Compare = std::less<std::array<long long int, 3> >]'
539 | priority_queue(const _Compare& __x, const _Sequence& __c,
| ^~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:539:2: note: template argument deduction/substitution failed:
Main.cpp:32:35: note: candidate expects 3 arguments, 1 provided
32 | priority_queue<array<ll,3>> pq(n);
| ^
In file included from /usr/include/c++/10/queue:64,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:533:2: note: candidate: 'template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, const _Alloc&) [with _Alloc = _Alloc; _Requires = _Requires; _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >; _Compare = std::less<std::array<long long int, 3> >]'
533 | priority_queue(const _Compare& __x, const _Alloc& __a)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:533:2: note: template argument deduction/substitution failed:
Main.cpp:32:35: note: candidate expects 2 arguments, 1 provided
32 | priority_queue<array<ll,3>> pq(n);
| ^
In file included from /usr/include/c++/10/queue:64,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:529:2: note: candidate: 'template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Alloc&) [with _Alloc = _Alloc; _Requires = _Requires; _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >; _Compare = std::less<std::array<long long int, 3> >]'
529 | priority_queue(const _Alloc& __a)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:529:2: note: template argument deduction/substitution failed:
/usr/include/c++/10/bits/stl_queue.h: In substitution of 'template<class _Tp, class _Sequence, class _Compare> template<class _Alloc> using _Uses = typename std::enable_if<std::uses_allocator<_Sequence, _Alloc>::value>::type [with _Alloc = int; _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >; _Compare = std::less<std::array<long long int, 3> >]':
/usr/include/c++/10/bits/stl_queue.h:527:33: required from here
/usr/include/c++/10/bits/stl_queue.h:473:8: error: no type named 'type' in 'struct std::enable_if<false, void>'
473 | using _Uses = typename
| ^~~~~
/usr/include/c++/10/bits/stl_queue.h:523:7: note: candidate: 'std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, _Sequence&&) [with _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >; _Compare = std::less<std::array<long long int, 3> >]'
523 | priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence())
| ^~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:523:38: note: no known conversion for argument 1 from 'int' to 'const std::less<std::array<long long int, 3> >&'
523 | priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence())
| ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:518:7: note: candidate: 'std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, const _Sequence&) [with _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >; _Compare = std::less<std::array<long long int, 3> >]'
518 | priority_queue(const _Compare& __x, const _Sequence& __s)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:518:7: note: candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_queue.h:514:2: note: candidate: 'template<class _Seq, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue() [with _Seq = _Seq; _Requires = _Requires; _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >; _Compare = std::less<std::array<long long int, 3> >]'
514 | priority_queue()
| ^~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:514:2: note: template argument deduction/substitution failed:
Main.cpp:32:35: note: candidate expects 0 arguments, 1 provided
32 | priority_queue<array<ll,3>> pq(n);
| ^
In file included from /usr/include/c++/10/queue:64,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:456:11: note: candidate: 'std::priority_queue<std::array<long long int, 3> >::priority_queue(const std::priority_queue<std::array<long long int, 3> >&)'
456 | class priority_queue
| ^~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:456:11: note: no known conversion for argument 1 from 'int' to 'const std::priority_queue<std::array<long long int, 3> >&'
/usr/include/c++/10/bits/stl_queue.h:456:11: note: candidate: 'std::priority_queue<std::array<long long int, 3> >::priority_queue(std::priority_queue<std::array<long long int, 3> >&&)'
/usr/include/c++/10/bits/stl_queue.h:456:11: note: no known conversion for argument 1 from 'int' to 'std::priority_queue<std::array<long long int, 3> >&&'
Main.cpp:37:16: error: no matching function for call to 'std::priority_queue<std::array<long long int, 3> >::push(int, int&, int)'
37 | pq.push(0,n,1);
| ^
In file included from /usr/include/c++/10/queue:64,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >; _Compare = std::less<std::array<long long int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<long long int, 3>]'
640 | push(const value_type& __x)
| ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate expects 1 argument, 3 provided
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3>, std::allocator<std::array<long long int, 3> > >; _Compare = std::less<std::array<long long int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<long long int, 3>]'
648 | push(value_type&& __x)
| ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate expects 1 argument, 3 provided