# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
483675 |
2021-10-31T15:16:11 Z |
Victor |
Robot (JOI21_ho_t4) |
C++17 |
|
958 ms |
83060 KB |
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int INF = 1'000'000'007;
int n, m;
vector<pair<int, pair<int, ll>>> graph[100001];
umap<int, ll> sums[100001];
umap<int, ll> dist[100001];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin >> n >> m;
rep(i, 0, m) {
int u, v, c;
ll w;
cin >> u >> v >> c >> w;
sums[--u][--c] += w;
sums[--v][c] += w;
graph[u].pb({c, {v, w}});
graph[v].pb({c, {u, w}});
}
rep(i, 0, n) sort(all(graph[i]));
set<pair<ll, ii>> pq;
dist[0][m]=0;
pq.insert({0, {0, m}});
while (!pq.empty()) {
ll d;
int u, color;
d = pq.begin()->first;
tie(u, color) = pq.begin()->second;
pq.erase(pq.begin());
//cout<<"u = "<<u + 1<<" d = "<<d<<" color = "<<color<<endl;
if (color == m) {
trav(edge, graph[u]) {
int ncolor = edge.first, v;
ll w, sum = sums[u][ncolor];
tie(v, w) = edge.second;
ll add = min(w, sum - w);
if (!dist[v].count(m)) dist[v][m] = ll(1e16);
if (d + add < dist[v][m]) {
pq.erase({dist[v][m], {v, m}});
pq.insert({d + add, {v, m}});
dist[v][m] = d + add;
}
if (!dist[v].count(ncolor)) dist[v][ncolor] = ll(1e16);
if (d < dist[v][ncolor]) {
pq.erase({dist[v][n], {v, ncolor}});
pq.insert({d, {v, ncolor}});
dist[v][ncolor] = d;
}
}
}
else {
const auto &cur_g = graph[u];
pair<int, pair<int, ll>> x = {color, {0, 0}};
int start = lower_bound(all(cur_g), x) - cur_g.begin();
x.first++;
int stop = lower_bound(all(cur_g), x) - cur_g.begin();
rep(i, start, stop) {
int v;
ll w, sum = sums[u][color];
tie(v, w) = cur_g[i].second;
ll add = sum - w;
if (!dist[v].count(m)) dist[v][m] = ll(1e16);
if (d + add < dist[v][m]) {
pq.erase({dist[v][m], {v, m}});
pq.insert({d + add, {v, m}});
dist[v][m] = d + add;
}
}
}
}
if (!dist[n-1].count(m)) dist[n-1][m] = -1;
cout<<dist[n-1][m]<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
13516 KB |
Output is correct |
2 |
Correct |
9 ms |
13628 KB |
Output is correct |
3 |
Correct |
7 ms |
13600 KB |
Output is correct |
4 |
Correct |
9 ms |
13624 KB |
Output is correct |
5 |
Correct |
7 ms |
13644 KB |
Output is correct |
6 |
Correct |
8 ms |
13624 KB |
Output is correct |
7 |
Correct |
8 ms |
13644 KB |
Output is correct |
8 |
Correct |
9 ms |
13700 KB |
Output is correct |
9 |
Correct |
11 ms |
14220 KB |
Output is correct |
10 |
Correct |
11 ms |
14272 KB |
Output is correct |
11 |
Correct |
9 ms |
14156 KB |
Output is correct |
12 |
Correct |
9 ms |
14088 KB |
Output is correct |
13 |
Correct |
9 ms |
14156 KB |
Output is correct |
14 |
Correct |
9 ms |
14164 KB |
Output is correct |
15 |
Correct |
8 ms |
14028 KB |
Output is correct |
16 |
Correct |
9 ms |
14156 KB |
Output is correct |
17 |
Correct |
9 ms |
14016 KB |
Output is correct |
18 |
Correct |
8 ms |
13732 KB |
Output is correct |
19 |
Correct |
9 ms |
13900 KB |
Output is correct |
20 |
Correct |
9 ms |
14028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
216 ms |
33012 KB |
Output is correct |
2 |
Correct |
96 ms |
23492 KB |
Output is correct |
3 |
Correct |
242 ms |
33224 KB |
Output is correct |
4 |
Correct |
143 ms |
28356 KB |
Output is correct |
5 |
Correct |
788 ms |
80116 KB |
Output is correct |
6 |
Correct |
658 ms |
75560 KB |
Output is correct |
7 |
Correct |
352 ms |
75540 KB |
Output is correct |
8 |
Correct |
475 ms |
65568 KB |
Output is correct |
9 |
Correct |
512 ms |
65612 KB |
Output is correct |
10 |
Correct |
354 ms |
44736 KB |
Output is correct |
11 |
Correct |
119 ms |
32540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
13516 KB |
Output is correct |
2 |
Correct |
9 ms |
13628 KB |
Output is correct |
3 |
Correct |
7 ms |
13600 KB |
Output is correct |
4 |
Correct |
9 ms |
13624 KB |
Output is correct |
5 |
Correct |
7 ms |
13644 KB |
Output is correct |
6 |
Correct |
8 ms |
13624 KB |
Output is correct |
7 |
Correct |
8 ms |
13644 KB |
Output is correct |
8 |
Correct |
9 ms |
13700 KB |
Output is correct |
9 |
Correct |
11 ms |
14220 KB |
Output is correct |
10 |
Correct |
11 ms |
14272 KB |
Output is correct |
11 |
Correct |
9 ms |
14156 KB |
Output is correct |
12 |
Correct |
9 ms |
14088 KB |
Output is correct |
13 |
Correct |
9 ms |
14156 KB |
Output is correct |
14 |
Correct |
9 ms |
14164 KB |
Output is correct |
15 |
Correct |
8 ms |
14028 KB |
Output is correct |
16 |
Correct |
9 ms |
14156 KB |
Output is correct |
17 |
Correct |
9 ms |
14016 KB |
Output is correct |
18 |
Correct |
8 ms |
13732 KB |
Output is correct |
19 |
Correct |
9 ms |
13900 KB |
Output is correct |
20 |
Correct |
9 ms |
14028 KB |
Output is correct |
21 |
Correct |
216 ms |
33012 KB |
Output is correct |
22 |
Correct |
96 ms |
23492 KB |
Output is correct |
23 |
Correct |
242 ms |
33224 KB |
Output is correct |
24 |
Correct |
143 ms |
28356 KB |
Output is correct |
25 |
Correct |
788 ms |
80116 KB |
Output is correct |
26 |
Correct |
658 ms |
75560 KB |
Output is correct |
27 |
Correct |
352 ms |
75540 KB |
Output is correct |
28 |
Correct |
475 ms |
65568 KB |
Output is correct |
29 |
Correct |
512 ms |
65612 KB |
Output is correct |
30 |
Correct |
354 ms |
44736 KB |
Output is correct |
31 |
Correct |
119 ms |
32540 KB |
Output is correct |
32 |
Correct |
147 ms |
28492 KB |
Output is correct |
33 |
Correct |
234 ms |
32524 KB |
Output is correct |
34 |
Correct |
534 ms |
46668 KB |
Output is correct |
35 |
Correct |
452 ms |
42284 KB |
Output is correct |
36 |
Correct |
415 ms |
59764 KB |
Output is correct |
37 |
Correct |
457 ms |
64828 KB |
Output is correct |
38 |
Correct |
443 ms |
75116 KB |
Output is correct |
39 |
Correct |
180 ms |
34364 KB |
Output is correct |
40 |
Correct |
538 ms |
66820 KB |
Output is correct |
41 |
Correct |
543 ms |
67000 KB |
Output is correct |
42 |
Correct |
645 ms |
62248 KB |
Output is correct |
43 |
Correct |
224 ms |
31868 KB |
Output is correct |
44 |
Correct |
434 ms |
39872 KB |
Output is correct |
45 |
Correct |
366 ms |
61948 KB |
Output is correct |
46 |
Correct |
346 ms |
61092 KB |
Output is correct |
47 |
Correct |
409 ms |
63368 KB |
Output is correct |
48 |
Correct |
958 ms |
83060 KB |
Output is correct |