# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
806620 |
2023-08-04T08:24:27 Z |
vjudge1 |
Robot (JOI21_ho_t4) |
C++17 |
|
623 ms |
45564 KB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
const ll INF = 1e16;
int n, m;
int C[M], P[M];
struct edge {
int to, i;
};
struct state {
int v, st, ix, color;
};
bool operator < (state x, state y) {
return (x.v < y.v);
}
vector<edge> g[N];
vector<int> order;
bool us[N];
pair<ll, int> dp[N][2][2];
map<ll, ll> S[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back({v, i});
g[v].push_back({u, i});
cin >> C[i] >> P[i];
}
for(int i = 1; i <= n; i++) {
for(auto [to, x] : g[i]) {
S[i][C[x]] += P[x];
}
}
set<pair<ll, state>> St;
for(int i = 1; i <= n; i++) {
dp[i][0][0] = dp[i][0][1] = {(i < n ? INF : 0), -1},
dp[i][1][0] = dp[i][1][1] = {(i < n ? INF : 0), -1};
for(int j = 0; j <= 1; j++) {
for(int k = 0; k <= 1; k++) {
St.insert({dp[i][j][k].first, {i, j, k, -1}});
}
}
}
bool processed[n + 1] = {};
while(!St.empty()) {
state t = (St.begin())->second;
int cur = t.v, st = t.st, ix = t.ix, color = t.color;
ll curdp = dp[cur][st][ix].first;
St.erase(St.begin());
processed[cur] = 1;
for(auto [to, i] : g[cur]) {
if(processed[to]) continue;
for(int next_st = 0; next_st <= 1; next_st++) {
St.erase({dp[to][next_st][0].first, {to, next_st, 0, dp[to][next_st][0].second}});
St.erase({dp[to][next_st][1].first, {to, next_st, 1, dp[to][next_st][1].second}});
ll newdp, cl = C[i];
if(next_st) newdp = curdp + (S[to][cl] - P[i]);
else newdp = curdp + P[i] * (cl != color || !st);
if(dp[to][next_st][0].second == cl)
dp[to][next_st][0].first = min(dp[to][next_st][0].first, newdp);
if(dp[to][next_st][1].second == cl)
dp[to][next_st][1].first = min(dp[to][next_st][1].first, newdp);
if(dp[to][next_st][0].first > dp[to][next_st][1].first)
swap(dp[to][next_st][0], dp[to][next_st][1]);
if(newdp < dp[to][next_st][0].first)
swap(dp[to][next_st][0], dp[to][next_st][1]),
dp[to][next_st][0] = {newdp, cl};
else if(newdp < dp[to][next_st][1].first)
dp[to][next_st][1] = {newdp, cl};
St.insert({dp[to][next_st][0].first, {to, next_st, 0, dp[to][next_st][0].second}});
St.insert({dp[to][next_st][1].first, {to, next_st, 1, dp[to][next_st][1].second}});
}
}
}
ll res = min(dp[1][0][0].first, dp[1][1][0].first);
cout << (res == INF ? -1 : res);
}
// for(int cur : order) {
// if(cur == n) {
// continue;
// }
// dp[cur][0][0] = dp[cur][0][1] = {INF, -1};
// dp[cur][1][0] = dp[cur][1][1] = {INF, -1};
// vector<pair<int, int>> pr;
// for(auto [to, i] : g[cur])
// if(tin[to] < tin[cur]) pr.push_back({to, i});
// map<int, int> S;
// map<int, ll> ans[2];
// for(auto [to, i] : g[cur]) {
// S[C[i]] += P[i];
// }
// for(auto [next, i] : pr) {
// for(int st = 0; st <= 1; st++) {
// ans[st][C[i]] = INF;
// for(int next_st = 0; next_st <= 1; next_st++) {
// ans[st][C[i]] = min(ans[st][C[i]], dp[next][next_st][0].first + (st ? S[C[i]] - P[i] : P[i]));
// }
// }
// ans[0][C[i]] = min(ans[0][C[i]], dp[next][1][0].first + (dp[next][1][0].second != C[i]) * P[i]);
// ans[0][C[i]] = min(ans[0][C[i]], dp[next][1][1].first + (dp[next][1][1].second != C[i]) * P[i]);
// }
// for(int st = 0; st <= 1; st++) {
// dp[cur][st][0] = {(--ans[st].end())->second, (--ans[st].end())->first};
// if((int)ans[st].size() > 1) {
// dp[cur][st][1] = {(--(--ans[st].end()))->second, (--(--ans[st].end()))->first};
// }
// }
// }
// ll res = INF;
// for(int st = 0; st <= 1; st++)
// res = min(dp[1][st][0].first, res);
// cout << (res == INF ? -1 : res);
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
3 ms |
7380 KB |
Output is correct |
3 |
Correct |
3 ms |
7380 KB |
Output is correct |
4 |
Correct |
3 ms |
7380 KB |
Output is correct |
5 |
Correct |
4 ms |
7380 KB |
Output is correct |
6 |
Correct |
3 ms |
7380 KB |
Output is correct |
7 |
Correct |
6 ms |
7380 KB |
Output is correct |
8 |
Correct |
3 ms |
7380 KB |
Output is correct |
9 |
Incorrect |
7 ms |
7784 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
192 ms |
19004 KB |
Output is correct |
2 |
Correct |
95 ms |
13568 KB |
Output is correct |
3 |
Correct |
266 ms |
17600 KB |
Output is correct |
4 |
Correct |
131 ms |
16308 KB |
Output is correct |
5 |
Incorrect |
623 ms |
45564 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
3 ms |
7380 KB |
Output is correct |
3 |
Correct |
3 ms |
7380 KB |
Output is correct |
4 |
Correct |
3 ms |
7380 KB |
Output is correct |
5 |
Correct |
4 ms |
7380 KB |
Output is correct |
6 |
Correct |
3 ms |
7380 KB |
Output is correct |
7 |
Correct |
6 ms |
7380 KB |
Output is correct |
8 |
Correct |
3 ms |
7380 KB |
Output is correct |
9 |
Incorrect |
7 ms |
7784 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |