# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
925317 |
2024-02-11T11:51:14 Z |
crafticat |
Robot (JOI21_ho_t4) |
C++17 |
|
3000 ms |
307964 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
constexpr ll inf = 1e12 + 7;
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
ll n, m; cin >> n >> m;
vector<vector<tuple<ll,ll,ll>>> f(n + 1);
for (ll i = 0; i < m; ++i) {
ll a, b, c, d; cin >> a >> b >> c >> d;
f[a].emplace_back(c,b,d);
f[b].emplace_back(c,a,d);
}
vector<vector<tuple<ll,ll,ll>>> g(n + 1);
vector<map<ll,ll>> apps(n + 1);
map<pii, pii> roads;
for (ll i = 1; i <= n; ++i) {
map<ll, ll> app;
for (auto [c, node, d] : f[i]) {
app[c]+=d;
}
apps[i] = app;
for (auto [c, node, d] : f[i]) {
roads[{i,node}] = {c,d};
roads[{node,i}] = {c,d};
g[i].emplace_back(node,d,c);
}
}
priority_queue<tuple<ll,ll,ll>,vector<tuple<ll,ll,ll>>,greater<>> pq;
pq.emplace(0,1,0);
vector<ll> d(n + 1,inf);
map<pii, ll> dp;
map<pii,bool> visited;
while (!pq.empty()) {
auto [cost, cur, par] = pq.top();pq.pop();
if (visited[{cur,par}]) continue;
d[cur] = min(d[cur],cost);
if (dp[{cur,roads[{cur,par}].first}] != 0) continue;
dp[{cur,roads[{cur,par}].first}] = cost;
visited[{cur,par}] = true;
for (auto [child, len, c] : g[cur]) {
if (child == par) continue;
if (visited[{child,cur}]) continue;
ll am = apps[cur][c];
if (c == roads[{par,cur}].first) am -= roads[{par,cur}].second;
pq.emplace(cost + len,child,cur);
pq.emplace(cost + am - len,child,-cur);
}
}
if (d[n] == inf) {
cout << "-1";
return 0;
}
cout << d[n];
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
14 ms |
1688 KB |
Output is correct |
8 |
Correct |
3 ms |
856 KB |
Output is correct |
9 |
Correct |
616 ms |
51440 KB |
Output is correct |
10 |
Correct |
341 ms |
26456 KB |
Output is correct |
11 |
Correct |
8 ms |
2136 KB |
Output is correct |
12 |
Incorrect |
7 ms |
1884 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1236 ms |
81728 KB |
Output is correct |
2 |
Correct |
418 ms |
38388 KB |
Output is correct |
3 |
Correct |
2257 ms |
119264 KB |
Output is correct |
4 |
Correct |
658 ms |
53864 KB |
Output is correct |
5 |
Execution timed out |
3066 ms |
307964 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
14 ms |
1688 KB |
Output is correct |
8 |
Correct |
3 ms |
856 KB |
Output is correct |
9 |
Correct |
616 ms |
51440 KB |
Output is correct |
10 |
Correct |
341 ms |
26456 KB |
Output is correct |
11 |
Correct |
8 ms |
2136 KB |
Output is correct |
12 |
Incorrect |
7 ms |
1884 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |