# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
927699 |
2024-02-15T08:50:17 Z |
LonlyR |
Robot (JOI21_ho_t4) |
C++17 |
|
890 ms |
117492 KB |
#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second
using namespace std;
const int maxn = 2e5 + 5;
int n, m;
int dp[maxn];
vector<array<int, 3>> adj[maxn];
map<int,int> col[maxn];
map<int,int> dpc[maxn];
map<int,vector<ii>> adjc[maxn];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
cin >> n >> m;
for (int i = 1, u, v, w, t; i <= m; i++)
{
cin >> u >> v >> w >> t;
adj[u].push_back({v, w, t});
adj[v].push_back({u, w, t});
adjc[u][w].emplace_back(v, t);
adjc[v][w].emplace_back(u, t);
col[u][w] += t;
col[v][w] += t;
}
#define iii tuple<int,int,int>
priority_queue<iii, vector<iii>, greater<iii>> pq;
memset(dp, 0x3f, sizeof dp);
int oo = dp[0];
dp[1] = 0;
pq.emplace(0, 1, 0);
while (pq.size())
{
int u, v, w;
tie(v, u, w) = pq.top();
pq.pop();
if (w == 0)
{
if (v != dp[u]) continue;
for (auto p : adj[u])
{
int color = p[1], cost = p[2], nxt = p[0];
int val = v + cost, f = 0;
if (dp[nxt] > val)
dp[nxt] = val,
f = 1;
if (!dpc[nxt].count(color) || dpc[nxt][color] > val - cost)
dpc[nxt][color] = val - cost,
pq.emplace(val - cost, nxt, color);
val = v + col[u][color] - cost;
if (dp[nxt] > val)
dp[nxt] = val,
f = 1;
if (f) pq.emplace(dp[nxt], nxt, 0);
}
}
else
{
if (v != dpc[u][w]) continue;
for (auto p : adjc[u][w])
{
int nxt = p.ff, cost = p.ss, color = w;
int val = v + col[u][color] - cost;
if (dp[nxt] > val)
dp[nxt] = val,
pq.emplace(dp[nxt], nxt, 0);
}
}
}
cout << (dp[n] == oo ? -1 : dp[n]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
34652 KB |
Output is correct |
2 |
Correct |
7 ms |
34768 KB |
Output is correct |
3 |
Correct |
7 ms |
34648 KB |
Output is correct |
4 |
Correct |
7 ms |
34652 KB |
Output is correct |
5 |
Correct |
8 ms |
34908 KB |
Output is correct |
6 |
Correct |
7 ms |
34908 KB |
Output is correct |
7 |
Correct |
9 ms |
35220 KB |
Output is correct |
8 |
Correct |
7 ms |
34908 KB |
Output is correct |
9 |
Correct |
11 ms |
35420 KB |
Output is correct |
10 |
Correct |
10 ms |
35420 KB |
Output is correct |
11 |
Correct |
9 ms |
35164 KB |
Output is correct |
12 |
Correct |
9 ms |
35160 KB |
Output is correct |
13 |
Correct |
9 ms |
35256 KB |
Output is correct |
14 |
Correct |
9 ms |
35268 KB |
Output is correct |
15 |
Correct |
9 ms |
35164 KB |
Output is correct |
16 |
Correct |
9 ms |
35164 KB |
Output is correct |
17 |
Correct |
10 ms |
35404 KB |
Output is correct |
18 |
Correct |
8 ms |
34908 KB |
Output is correct |
19 |
Correct |
9 ms |
35328 KB |
Output is correct |
20 |
Correct |
9 ms |
35164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
196 ms |
59196 KB |
Output is correct |
2 |
Correct |
64 ms |
46736 KB |
Output is correct |
3 |
Correct |
152 ms |
60112 KB |
Output is correct |
4 |
Correct |
93 ms |
50868 KB |
Output is correct |
5 |
Correct |
890 ms |
112956 KB |
Output is correct |
6 |
Correct |
722 ms |
105944 KB |
Output is correct |
7 |
Correct |
337 ms |
86304 KB |
Output is correct |
8 |
Correct |
403 ms |
84312 KB |
Output is correct |
9 |
Correct |
459 ms |
84556 KB |
Output is correct |
10 |
Correct |
286 ms |
76196 KB |
Output is correct |
11 |
Correct |
135 ms |
59072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
34652 KB |
Output is correct |
2 |
Correct |
7 ms |
34768 KB |
Output is correct |
3 |
Correct |
7 ms |
34648 KB |
Output is correct |
4 |
Correct |
7 ms |
34652 KB |
Output is correct |
5 |
Correct |
8 ms |
34908 KB |
Output is correct |
6 |
Correct |
7 ms |
34908 KB |
Output is correct |
7 |
Correct |
9 ms |
35220 KB |
Output is correct |
8 |
Correct |
7 ms |
34908 KB |
Output is correct |
9 |
Correct |
11 ms |
35420 KB |
Output is correct |
10 |
Correct |
10 ms |
35420 KB |
Output is correct |
11 |
Correct |
9 ms |
35164 KB |
Output is correct |
12 |
Correct |
9 ms |
35160 KB |
Output is correct |
13 |
Correct |
9 ms |
35256 KB |
Output is correct |
14 |
Correct |
9 ms |
35268 KB |
Output is correct |
15 |
Correct |
9 ms |
35164 KB |
Output is correct |
16 |
Correct |
9 ms |
35164 KB |
Output is correct |
17 |
Correct |
10 ms |
35404 KB |
Output is correct |
18 |
Correct |
8 ms |
34908 KB |
Output is correct |
19 |
Correct |
9 ms |
35328 KB |
Output is correct |
20 |
Correct |
9 ms |
35164 KB |
Output is correct |
21 |
Correct |
196 ms |
59196 KB |
Output is correct |
22 |
Correct |
64 ms |
46736 KB |
Output is correct |
23 |
Correct |
152 ms |
60112 KB |
Output is correct |
24 |
Correct |
93 ms |
50868 KB |
Output is correct |
25 |
Correct |
890 ms |
112956 KB |
Output is correct |
26 |
Correct |
722 ms |
105944 KB |
Output is correct |
27 |
Correct |
337 ms |
86304 KB |
Output is correct |
28 |
Correct |
403 ms |
84312 KB |
Output is correct |
29 |
Correct |
459 ms |
84556 KB |
Output is correct |
30 |
Correct |
286 ms |
76196 KB |
Output is correct |
31 |
Correct |
135 ms |
59072 KB |
Output is correct |
32 |
Correct |
120 ms |
59220 KB |
Output is correct |
33 |
Correct |
121 ms |
60108 KB |
Output is correct |
34 |
Correct |
347 ms |
81148 KB |
Output is correct |
35 |
Correct |
257 ms |
70668 KB |
Output is correct |
36 |
Correct |
299 ms |
74288 KB |
Output is correct |
37 |
Correct |
333 ms |
80668 KB |
Output is correct |
38 |
Correct |
310 ms |
93840 KB |
Output is correct |
39 |
Correct |
129 ms |
66696 KB |
Output is correct |
40 |
Correct |
450 ms |
85492 KB |
Output is correct |
41 |
Correct |
455 ms |
85944 KB |
Output is correct |
42 |
Correct |
462 ms |
93980 KB |
Output is correct |
43 |
Correct |
190 ms |
63748 KB |
Output is correct |
44 |
Correct |
301 ms |
77752 KB |
Output is correct |
45 |
Correct |
315 ms |
77892 KB |
Output is correct |
46 |
Correct |
269 ms |
77012 KB |
Output is correct |
47 |
Correct |
293 ms |
79016 KB |
Output is correct |
48 |
Correct |
862 ms |
117492 KB |
Output is correct |