# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
970855 |
2024-04-27T11:37:19 Z |
htphong0909 |
Robot (JOI21_ho_t4) |
C++17 |
|
3000 ms |
37308 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define int long long
using namespace std;
vector<array<int, 3>> adj[100001];
vector<int> D[100001];
int sum[200001];
int sz[100001];
vector<int> id[100001];
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("TEST.in", "r", stdin);
//freopen("TEST.out", "w", stdout);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v, c, w;
cin >> u >> v >> c >> w;
adj[u].push_back({v, c, w});
adj[v].push_back({u, c, w});
id[u].push_back((int)adj[v].size() - 1);
id[v].push_back((int)adj[u].size() - 1);
}
for (int i = 1; i <= n; i++)
{
sz[i] = (int)adj[i].size();
D[i].resize(sz[i] + 1);
}
D[1][sz[1]] = 1;
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> q;
q.push({1, 1, sz[1]});
while (!q.empty())
{
int u = q.top()[1];
int t = q.top()[2];
int pc, pw;
if (t == sz[u]) tie(pc, pw) = make_pair(-1, 0);
else
{
pc = adj[u][t][1];
pw = adj[u][t][2];
}
q.pop();
for (int i = 0; i < sz[u]; i++) sum[adj[u][i][1]] = 0;
for (int i = 0; i < sz[u]; i++) sum[adj[u][i][1]] += adj[u][i][2];
for (int i = 0; i < sz[u]; i++)
{
int v = adj[u][i][0];
int c = adj[u][i][1];
int w = adj[u][i][2];
int s = sum[c];
int k = id[u][i];
if (pc == c) s -= pw;
if (t != sz[u] && v == adj[u][t][0]) continue;
if (D[u][t] + w < D[v][k] || !D[v][k])
{
D[v][k] = D[u][t] + w;
q.push({D[v][k], v, k});
}
if (D[u][t] + s - w < D[v][sz[v]] || !D[v][sz[v]])
{
D[v][sz[v]] = D[u][t] + s - w;
q.push({D[v][sz[v]], v, sz[v]});
}
}
}
int ans = (int)1e18;
for (int i = 0; i <= sz[n]; i++) ans = min(ans, D[n][i]);
if (ans == (int)1e18) cout << -1;
else cout << ans - 1;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9820 KB |
Output is correct |
2 |
Correct |
3 ms |
9820 KB |
Output is correct |
3 |
Correct |
2 ms |
9820 KB |
Output is correct |
4 |
Correct |
2 ms |
9820 KB |
Output is correct |
5 |
Correct |
2 ms |
9652 KB |
Output is correct |
6 |
Correct |
2 ms |
9820 KB |
Output is correct |
7 |
Correct |
3 ms |
9816 KB |
Output is correct |
8 |
Correct |
3 ms |
9820 KB |
Output is correct |
9 |
Correct |
14 ms |
10072 KB |
Output is correct |
10 |
Correct |
12 ms |
10076 KB |
Output is correct |
11 |
Correct |
21 ms |
10076 KB |
Output is correct |
12 |
Correct |
9 ms |
10072 KB |
Output is correct |
13 |
Correct |
20 ms |
10076 KB |
Output is correct |
14 |
Correct |
22 ms |
10076 KB |
Output is correct |
15 |
Correct |
4 ms |
9820 KB |
Output is correct |
16 |
Correct |
4 ms |
10076 KB |
Output is correct |
17 |
Correct |
3 ms |
10076 KB |
Output is correct |
18 |
Correct |
3 ms |
9820 KB |
Output is correct |
19 |
Correct |
6 ms |
10076 KB |
Output is correct |
20 |
Correct |
4 ms |
9820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
23752 KB |
Output is correct |
2 |
Correct |
43 ms |
15576 KB |
Output is correct |
3 |
Correct |
204 ms |
32452 KB |
Output is correct |
4 |
Correct |
68 ms |
19916 KB |
Output is correct |
5 |
Execution timed out |
3048 ms |
37308 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9820 KB |
Output is correct |
2 |
Correct |
3 ms |
9820 KB |
Output is correct |
3 |
Correct |
2 ms |
9820 KB |
Output is correct |
4 |
Correct |
2 ms |
9820 KB |
Output is correct |
5 |
Correct |
2 ms |
9652 KB |
Output is correct |
6 |
Correct |
2 ms |
9820 KB |
Output is correct |
7 |
Correct |
3 ms |
9816 KB |
Output is correct |
8 |
Correct |
3 ms |
9820 KB |
Output is correct |
9 |
Correct |
14 ms |
10072 KB |
Output is correct |
10 |
Correct |
12 ms |
10076 KB |
Output is correct |
11 |
Correct |
21 ms |
10076 KB |
Output is correct |
12 |
Correct |
9 ms |
10072 KB |
Output is correct |
13 |
Correct |
20 ms |
10076 KB |
Output is correct |
14 |
Correct |
22 ms |
10076 KB |
Output is correct |
15 |
Correct |
4 ms |
9820 KB |
Output is correct |
16 |
Correct |
4 ms |
10076 KB |
Output is correct |
17 |
Correct |
3 ms |
10076 KB |
Output is correct |
18 |
Correct |
3 ms |
9820 KB |
Output is correct |
19 |
Correct |
6 ms |
10076 KB |
Output is correct |
20 |
Correct |
4 ms |
9820 KB |
Output is correct |
21 |
Correct |
103 ms |
23752 KB |
Output is correct |
22 |
Correct |
43 ms |
15576 KB |
Output is correct |
23 |
Correct |
204 ms |
32452 KB |
Output is correct |
24 |
Correct |
68 ms |
19916 KB |
Output is correct |
25 |
Execution timed out |
3048 ms |
37308 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |