# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
773877 |
2023-07-05T09:15:10 Z |
mcdx9524 |
Robot (JOI21_ho_t4) |
C++17 |
|
3000 ms |
142900 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const long long inf = 1e18 + 7;
struct edge {
int to, color;
long long price;
int global_index;
};
struct info {
int to;
long long cost;
int index, global_index;
};
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector <vector <edge> > g(n);
vector <edge> edges;
for (int i = 0; i < m; i++) {
int a, b, c, p;
cin >> a >> b >> c >> p;
a--, b--;
g[a].push_back({b, c, p, i});
g[b].push_back({a, c, p, i});
edges.push_back({-1, c, p, i});
}
unordered_map <int, int> total_price;
vector <vector <info> > cg(n);
map <pair <int, int>, int> global;
map <pair <int, int>, int> global_rev;
unordered_map <int, int> global_price;
for (int i = 0; i < n; i++) {
for (auto [to, color, price, _] : g[i]) {
total_price[color] += price;
}
int index = 0;
for (auto [to, color, price, global_index] : g[i]) {
global[{i, index}] = global_index;
global_rev[{i, global_index}] = index;
global_price[global_index] = price;
cg[i].push_back({to, total_price[color] - price, -1, global_index});
cg[i].push_back({to, price, index, global_index});
index++;
}
for (auto [to, color, price, _] : g[i]) {
total_price[color] -= price;
}
}
priority_queue <tuple <long long, int, int> > q;
q.push({0, 0, -1});
vector <vector <long long> > d(n);
for (int i = 0; i < n; i++) {
d[i].resize((int) g[i].size() + 1, inf);
}
d[0][0] = 0;
while (!q.empty()) {
auto [cost, v, id] = q.top();
q.pop();
if (-cost > d[v][id + 1]) {
continue;
}
for (int i = 0; i < (int) cg[v].size(); i++) {
auto [to, new_cost, index, global_index] = cg[v][i];
int actual_index = -1;
if (index != -1) {
actual_index = global_rev[{to, global_index}];
} else if (id != -1) {
int global_id = global[{v, id}];
int incoming_color = edges[global_id].color;
int outgoing_color = edges[global_index].color;
if (incoming_color == outgoing_color) {
new_cost -= edges[global_id].price;
}
}
if (d[to][actual_index + 1] > d[v][id + 1] + new_cost) {
d[to][actual_index + 1] = d[v][id + 1] + new_cost;
q.push({-d[to][actual_index + 1], to, actual_index});
}
}
}
ll mn = inf;
for (int i = 0; i < (int) g[n - 1].size() + 1; i++) {
mn = min(mn, d[n - 1][i]);
}
cout << (mn == inf ? -1 : mn) << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
328 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
6 ms |
852 KB |
Output is correct |
8 |
Correct |
4 ms |
584 KB |
Output is correct |
9 |
Correct |
159 ms |
1704 KB |
Output is correct |
10 |
Correct |
118 ms |
1728 KB |
Output is correct |
11 |
Correct |
209 ms |
1704 KB |
Output is correct |
12 |
Correct |
71 ms |
1492 KB |
Output is correct |
13 |
Correct |
230 ms |
1748 KB |
Output is correct |
14 |
Correct |
203 ms |
1744 KB |
Output is correct |
15 |
Correct |
2 ms |
980 KB |
Output is correct |
16 |
Correct |
7 ms |
1608 KB |
Output is correct |
17 |
Correct |
5 ms |
1364 KB |
Output is correct |
18 |
Correct |
2 ms |
720 KB |
Output is correct |
19 |
Correct |
28 ms |
1748 KB |
Output is correct |
20 |
Correct |
4 ms |
1236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
681 ms |
57372 KB |
Output is correct |
2 |
Correct |
216 ms |
25624 KB |
Output is correct |
3 |
Correct |
1761 ms |
97860 KB |
Output is correct |
4 |
Correct |
362 ms |
39140 KB |
Output is correct |
5 |
Execution timed out |
3082 ms |
142900 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
328 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
6 ms |
852 KB |
Output is correct |
8 |
Correct |
4 ms |
584 KB |
Output is correct |
9 |
Correct |
159 ms |
1704 KB |
Output is correct |
10 |
Correct |
118 ms |
1728 KB |
Output is correct |
11 |
Correct |
209 ms |
1704 KB |
Output is correct |
12 |
Correct |
71 ms |
1492 KB |
Output is correct |
13 |
Correct |
230 ms |
1748 KB |
Output is correct |
14 |
Correct |
203 ms |
1744 KB |
Output is correct |
15 |
Correct |
2 ms |
980 KB |
Output is correct |
16 |
Correct |
7 ms |
1608 KB |
Output is correct |
17 |
Correct |
5 ms |
1364 KB |
Output is correct |
18 |
Correct |
2 ms |
720 KB |
Output is correct |
19 |
Correct |
28 ms |
1748 KB |
Output is correct |
20 |
Correct |
4 ms |
1236 KB |
Output is correct |
21 |
Correct |
681 ms |
57372 KB |
Output is correct |
22 |
Correct |
216 ms |
25624 KB |
Output is correct |
23 |
Correct |
1761 ms |
97860 KB |
Output is correct |
24 |
Correct |
362 ms |
39140 KB |
Output is correct |
25 |
Execution timed out |
3082 ms |
142900 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |