# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
382723 |
2021-03-28T06:09:56 Z |
jainbot27 |
Robot (JOI21_ho_t4) |
C++17 |
|
3000 ms |
551708 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;
ll d[mxN*10];
//vector<vector<pair<int, ll>>> g;
vector<pair<int, ll>> g[mxN*10];
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});
}
}
}
}
using F = pair<ll, int>;
priority_queue<F, vector<F>, greater<F>> pq;
pq.push({0, 0});
F0R(i, sz+1) d[i] = infLL;
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 |
17 ms |
26220 KB |
Output is correct |
2 |
Correct |
17 ms |
26220 KB |
Output is correct |
3 |
Correct |
17 ms |
26220 KB |
Output is correct |
4 |
Correct |
18 ms |
26220 KB |
Output is correct |
5 |
Correct |
17 ms |
26220 KB |
Output is correct |
6 |
Execution timed out |
3106 ms |
551708 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
142 ms |
42596 KB |
Output is correct |
2 |
Correct |
68 ms |
33520 KB |
Output is correct |
3 |
Correct |
186 ms |
52968 KB |
Output is correct |
4 |
Correct |
96 ms |
37224 KB |
Output is correct |
5 |
Correct |
260 ms |
60312 KB |
Output is correct |
6 |
Correct |
291 ms |
62904 KB |
Output is correct |
7 |
Correct |
244 ms |
69060 KB |
Output is correct |
8 |
Correct |
436 ms |
68588 KB |
Output is correct |
9 |
Correct |
451 ms |
68660 KB |
Output is correct |
10 |
Correct |
209 ms |
49132 KB |
Output is correct |
11 |
Correct |
181 ms |
46060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
26220 KB |
Output is correct |
2 |
Correct |
17 ms |
26220 KB |
Output is correct |
3 |
Correct |
17 ms |
26220 KB |
Output is correct |
4 |
Correct |
18 ms |
26220 KB |
Output is correct |
5 |
Correct |
17 ms |
26220 KB |
Output is correct |
6 |
Execution timed out |
3106 ms |
551708 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |