# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
382712 |
2021-03-28T05:59:36 Z |
jainbot27 |
Robot (JOI21_ho_t4) |
C++17 |
|
3000 ms |
20896 KB |
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()
#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl = '\n';
const int mxN = 1e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
int n, m;
vector<ll> d;
vector<vector<pair<int, ll>>> g;
vector<pair<int, pii>> v[mxN];
int32_t main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
F0R(i, m){
int a, b, c, p; cin >> a >> b >> c >> p;
a--; b--;
v[a].pb({c, {p, b}});
v[b].pb({c, {p, a}});
}
int sz = n-1;
g.resize(n);
d.resize(n, infLL);
F0R(i, n){
sort(all(v[i]));
for(int l=0, r=0; l<siz(v[i]); l=r){
ll sum = 0;
while(r<siz(v[i])&&v[i][l].f==v[i][r].f) sum += v[i][r++].s.f;
if(r-l==1) g[i].pb({0, v[i][l].s.s});
else{
g.pb({});
d.pb(infLL);
g[i].pb({0, ++sz});
FOR(j, l, r){
pii x = v[i][j].s;
g[i].pb(x);
g[x.s].pb({0, sz});
g[sz].pb({sum-x.f, x.s});
}
}
}
}
priority_queue<pair<ll, int>> pq;
pq.push({0, 0});
d[0] = 0;
while(!pq.empty()){
auto T = pq.top(); pq.pop();
if(d[T.s]!=T.f) continue;
trav(v, g[T.s]){
if(ckmin(d[v.s], T.f+v.f)){
pq.push({T.f+v.f, v.s});
}
}
}
cout << (d[n-1]==infLL?-1:d[n-1]) << nl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2668 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2668 KB |
Output is correct |
4 |
Correct |
2 ms |
2668 KB |
Output is correct |
5 |
Correct |
3 ms |
2668 KB |
Output is correct |
6 |
Execution timed out |
3068 ms |
2668 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3071 ms |
20896 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2668 KB |
Output is correct |
2 |
Correct |
2 ms |
2668 KB |
Output is correct |
3 |
Correct |
2 ms |
2668 KB |
Output is correct |
4 |
Correct |
2 ms |
2668 KB |
Output is correct |
5 |
Correct |
3 ms |
2668 KB |
Output is correct |
6 |
Execution timed out |
3068 ms |
2668 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |