#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, bool> plb;
typedef pair<ll, int> pli;
const int MAXN = 2000;
const int MAXM = 12000;
const int MAX_PATH = 1e5;
const ll inf = 1e15;
class path {
public:
ll len;
int s, e;
path(ll l, int s, int e) : len(l), s(s), e(e) {}
path() {}
};
vector<int> edges[MAXN];
pii init_edge[2*MAXN]; // dest, weight
vector<int> dual[MAXM];
int ecount = 0;
int make_edge() {
return (ecount++);
}
path dist[MAXN][MAXN][5]; // 0 : normal, 1 : first diff, 2 : f/e, 3 : e, 4 : e/f
ll edge_dist[2*MAXN][2*MAXN];
bool vis[MAXM]; // bitset?
int seq[MAX_PATH];
int n, m, t, l;
path min(path a, path b) {
if (a.len <= b.len) return a;
return b;
}
path comb(path a, path b) {
assert(a.e != b.s);
if (a.len == inf || b.len == inf) return path(inf, -1, -2);
return path(a.len+b.len, a.s, b.e);
}
class stree {
public:
int lp, rp;
stree *l = nullptr;
stree *r = nullptr;
path seg[5];
stree(int lv, int rv) {
lp = lv;
rp = rv;
if (lp < rp) {
int mid = (lp+rp)/2;
l = new stree(lp, mid);
r = new stree(mid+1, rp);
}
make();
}
int rdiff(int a) {
if (a == 0) return 3;
return 2;
}
void avoid(path seg[], int s, int e, int &a) { // best path avoiding these things
if (seg[a].s == s) a = 1;
if (seg[a].e == e) a = rdiff(a);
if (seg[a].s == s) a++;
}
void make() { // really slow. Could probably be faster
if (lp == rp) {
for (int i = 0; i < 5; i++) seg[i] = dist[seq[lp]][seq[lp+1]][i];
return;
}
for (int i = 0; i < 5; i++) {
int a = 0, b = 0;
int lv = -2, rv = -2;
if (i == 1 || i == 2) lv = seg[0].s;
if (i == 4) lv = seg[3].s;
if (i == 2) rv = seg[1].e;
if (i == 3 || i == 4) rv = seg[0].e;
avoid(l->seg, lv, -2, a);
avoid(r->seg, l->seg[a].e, rv, b);
seg[i] = comb(l->seg[a], r->seg[b]);
a = 0, b = 0;
avoid(r->seg, -2, rv, b);
avoid(l->seg, lv, r->seg[b].s, a);
seg[i] = min(seg[i], comb(l->seg[a], r->seg[b]));
}
}
void upd(int p) {
if (lp > p || rp < p) return;
if (lp == rp) return make();
l->upd(p);
r->upd(p);
make();
}
};
stree *tree;
void dijkstra(int s) {
fill(edge_dist[s], edge_dist[s]+2*m, inf);
fill(vis, vis+MAXM, 0); // could optimize by expanding dists to make pq smaller
priority_queue<pli, vector<pli>, greater<pli>> pq;
pq.push(pli(init_edge[s].second, s));
while (!pq.empty()) {
pli tp = pq.top();
pq.pop();
if (vis[tp.second]) continue;
if (tp.second < 2*m) edge_dist[s][tp.second] = tp.first;
vis[tp.second] = 1;
for (int nxt: dual[tp.second]) {
if (vis[nxt]) continue;
ll ndist = tp.first+((nxt<2*m) ? init_edge[nxt].second : 0);
pq.push(pli(ndist, nxt));
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> m >> t >> l;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c; a--; b--;
init_edge[2*i] = pii(b, c);
init_edge[2*i+1] = pii(a, c);
edges[a].push_back(make_edge());
edges[b].push_back(make_edge());
}
for (int i = 0; i < n; i++) {
vector<int> pref;
vector<int> suf;
for (int j = 0; j < edges[i].size(); j++) {
pref.push_back(make_edge());
dual[pref.back()].push_back(edges[i][j]);
}
for (int j = 0; j < edges[i].size(); j++) {
suf.push_back(make_edge());
dual[suf.back()].push_back(edges[i][j]);
}
for (int j = 1; j < edges[i].size(); j++) {
dual[pref[j]].push_back(pref[j-1]);
dual[suf[j-1]].push_back(suf[j]);
}
for (int j = 0; j < edges[i].size(); j++) {
if (j)dual[edges[i][j]^1].push_back(pref[j-1]);
if (j<edges[i].size()-1)dual[edges[i][j]^1].push_back(suf[j+1]);
}
}
for (int i = 0; i < 2*m; i++) dijkstra(i); // much cleaner?
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j][0] = path(inf, -1, -2);
for (int a: edges[i]) {
for (int b: edges[j]) {
dist[i][j][0] = min(dist[i][j][0], path(edge_dist[a][b^1], a, b));
}
}
// 1
dist[i][j][1] = path(inf, -1, -2);
for (int a: edges[i]) {
if (a == dist[i][j][0].s) continue;
for (int b: edges[j]) {
dist[i][j][1] = min(dist[i][j][1], path(edge_dist[a][b^1], a, b));
}
}
// 2
dist[i][j][2] = path(inf, -1, -2);
for (int a: edges[i]) {
if (a == dist[i][j][0].s) continue;
for (int b: edges[j]) {
if (b == dist[i][j][1].e) continue;
dist[i][j][2] = min(dist[i][j][2], path(edge_dist[a][b^1], a, b));
}
}
// 3
dist[i][j][3] = path(inf, -1, -2);
for (int a: edges[i]) {
for (int b: edges[j]) {
if (b == dist[i][j][0].e) continue;
dist[i][j][3] = min(dist[i][j][3], path(edge_dist[a][b^1], a, b));
}
}
// 4
dist[i][j][4] = path(inf, -1, -2);
for (int a: edges[i]) {
if (a == dist[i][j][3].s) continue;
for (int b: edges[j]) {
if (b == dist[i][j][0].e) continue;
dist[i][j][4] = min(dist[i][j][4], path(edge_dist[a][b^1], a, b));
}
}
}
}
for (int i = 0; i < l; i++) {
cin >> seq[i];
seq[i]--;
}
tree = new stree(0, l-2);
for (int i = 0; i < t; i++) {
int x, v; cin >> x >> v;
x--; v--;
seq[x] = v;
if (x) tree->upd(x-1);
if (x < l-1) tree->upd(x);
if (tree->seg[0].len == inf) cout << "-1\n";
else cout << tree->seg[0].len << "\n";
}
return 0;
}
Compilation message
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:138:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for (int j = 0; j < edges[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
wild_boar.cpp:142:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for (int j = 0; j < edges[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
wild_boar.cpp:146:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for (int j = 1; j < edges[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
wild_boar.cpp:150:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for (int j = 0; j < edges[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
wild_boar.cpp:152:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | if (j<edges[i].size()-1)dual[edges[i][j]^1].push_back(suf[j+1]);
| ~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
672 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
800 KB |
Output is correct |
11 |
Correct |
2 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
724 KB |
Output is correct |
14 |
Correct |
1 ms |
724 KB |
Output is correct |
15 |
Correct |
1 ms |
800 KB |
Output is correct |
16 |
Correct |
1 ms |
724 KB |
Output is correct |
17 |
Correct |
1 ms |
800 KB |
Output is correct |
18 |
Correct |
1 ms |
724 KB |
Output is correct |
19 |
Correct |
1 ms |
724 KB |
Output is correct |
20 |
Correct |
1 ms |
724 KB |
Output is correct |
21 |
Correct |
1 ms |
724 KB |
Output is correct |
22 |
Correct |
1 ms |
724 KB |
Output is correct |
23 |
Correct |
1 ms |
664 KB |
Output is correct |
24 |
Correct |
1 ms |
664 KB |
Output is correct |
25 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
672 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
800 KB |
Output is correct |
11 |
Correct |
2 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
724 KB |
Output is correct |
14 |
Correct |
1 ms |
724 KB |
Output is correct |
15 |
Correct |
1 ms |
800 KB |
Output is correct |
16 |
Correct |
1 ms |
724 KB |
Output is correct |
17 |
Correct |
1 ms |
800 KB |
Output is correct |
18 |
Correct |
1 ms |
724 KB |
Output is correct |
19 |
Correct |
1 ms |
724 KB |
Output is correct |
20 |
Correct |
1 ms |
724 KB |
Output is correct |
21 |
Correct |
1 ms |
724 KB |
Output is correct |
22 |
Correct |
1 ms |
724 KB |
Output is correct |
23 |
Correct |
1 ms |
664 KB |
Output is correct |
24 |
Correct |
1 ms |
664 KB |
Output is correct |
25 |
Correct |
1 ms |
724 KB |
Output is correct |
26 |
Correct |
3 ms |
1108 KB |
Output is correct |
27 |
Correct |
32 ms |
25576 KB |
Output is correct |
28 |
Correct |
33 ms |
25596 KB |
Output is correct |
29 |
Correct |
136 ms |
29676 KB |
Output is correct |
30 |
Correct |
127 ms |
29524 KB |
Output is correct |
31 |
Correct |
123 ms |
29516 KB |
Output is correct |
32 |
Correct |
127 ms |
29564 KB |
Output is correct |
33 |
Correct |
128 ms |
30816 KB |
Output is correct |
34 |
Correct |
120 ms |
30796 KB |
Output is correct |
35 |
Correct |
107 ms |
30668 KB |
Output is correct |
36 |
Correct |
115 ms |
30692 KB |
Output is correct |
37 |
Correct |
117 ms |
30884 KB |
Output is correct |
38 |
Correct |
119 ms |
32400 KB |
Output is correct |
39 |
Correct |
96 ms |
32296 KB |
Output is correct |
40 |
Correct |
110 ms |
32428 KB |
Output is correct |
41 |
Correct |
105 ms |
32444 KB |
Output is correct |
42 |
Correct |
85 ms |
33500 KB |
Output is correct |
43 |
Correct |
93 ms |
34420 KB |
Output is correct |
44 |
Correct |
91 ms |
34472 KB |
Output is correct |
45 |
Incorrect |
54 ms |
36768 KB |
Output isn't correct |
46 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
672 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
800 KB |
Output is correct |
11 |
Correct |
2 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
724 KB |
Output is correct |
14 |
Correct |
1 ms |
724 KB |
Output is correct |
15 |
Correct |
1 ms |
800 KB |
Output is correct |
16 |
Correct |
1 ms |
724 KB |
Output is correct |
17 |
Correct |
1 ms |
800 KB |
Output is correct |
18 |
Correct |
1 ms |
724 KB |
Output is correct |
19 |
Correct |
1 ms |
724 KB |
Output is correct |
20 |
Correct |
1 ms |
724 KB |
Output is correct |
21 |
Correct |
1 ms |
724 KB |
Output is correct |
22 |
Correct |
1 ms |
724 KB |
Output is correct |
23 |
Correct |
1 ms |
664 KB |
Output is correct |
24 |
Correct |
1 ms |
664 KB |
Output is correct |
25 |
Correct |
1 ms |
724 KB |
Output is correct |
26 |
Correct |
3 ms |
1108 KB |
Output is correct |
27 |
Correct |
32 ms |
25576 KB |
Output is correct |
28 |
Correct |
33 ms |
25596 KB |
Output is correct |
29 |
Correct |
136 ms |
29676 KB |
Output is correct |
30 |
Correct |
127 ms |
29524 KB |
Output is correct |
31 |
Correct |
123 ms |
29516 KB |
Output is correct |
32 |
Correct |
127 ms |
29564 KB |
Output is correct |
33 |
Correct |
128 ms |
30816 KB |
Output is correct |
34 |
Correct |
120 ms |
30796 KB |
Output is correct |
35 |
Correct |
107 ms |
30668 KB |
Output is correct |
36 |
Correct |
115 ms |
30692 KB |
Output is correct |
37 |
Correct |
117 ms |
30884 KB |
Output is correct |
38 |
Correct |
119 ms |
32400 KB |
Output is correct |
39 |
Correct |
96 ms |
32296 KB |
Output is correct |
40 |
Correct |
110 ms |
32428 KB |
Output is correct |
41 |
Correct |
105 ms |
32444 KB |
Output is correct |
42 |
Correct |
85 ms |
33500 KB |
Output is correct |
43 |
Correct |
93 ms |
34420 KB |
Output is correct |
44 |
Correct |
91 ms |
34472 KB |
Output is correct |
45 |
Incorrect |
54 ms |
36768 KB |
Output isn't correct |
46 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
672 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
800 KB |
Output is correct |
11 |
Correct |
2 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
724 KB |
Output is correct |
14 |
Correct |
1 ms |
724 KB |
Output is correct |
15 |
Correct |
1 ms |
800 KB |
Output is correct |
16 |
Correct |
1 ms |
724 KB |
Output is correct |
17 |
Correct |
1 ms |
800 KB |
Output is correct |
18 |
Correct |
1 ms |
724 KB |
Output is correct |
19 |
Correct |
1 ms |
724 KB |
Output is correct |
20 |
Correct |
1 ms |
724 KB |
Output is correct |
21 |
Correct |
1 ms |
724 KB |
Output is correct |
22 |
Correct |
1 ms |
724 KB |
Output is correct |
23 |
Correct |
1 ms |
664 KB |
Output is correct |
24 |
Correct |
1 ms |
664 KB |
Output is correct |
25 |
Correct |
1 ms |
724 KB |
Output is correct |
26 |
Correct |
3 ms |
1108 KB |
Output is correct |
27 |
Correct |
32 ms |
25576 KB |
Output is correct |
28 |
Correct |
33 ms |
25596 KB |
Output is correct |
29 |
Correct |
136 ms |
29676 KB |
Output is correct |
30 |
Correct |
127 ms |
29524 KB |
Output is correct |
31 |
Correct |
123 ms |
29516 KB |
Output is correct |
32 |
Correct |
127 ms |
29564 KB |
Output is correct |
33 |
Correct |
128 ms |
30816 KB |
Output is correct |
34 |
Correct |
120 ms |
30796 KB |
Output is correct |
35 |
Correct |
107 ms |
30668 KB |
Output is correct |
36 |
Correct |
115 ms |
30692 KB |
Output is correct |
37 |
Correct |
117 ms |
30884 KB |
Output is correct |
38 |
Correct |
119 ms |
32400 KB |
Output is correct |
39 |
Correct |
96 ms |
32296 KB |
Output is correct |
40 |
Correct |
110 ms |
32428 KB |
Output is correct |
41 |
Correct |
105 ms |
32444 KB |
Output is correct |
42 |
Correct |
85 ms |
33500 KB |
Output is correct |
43 |
Correct |
93 ms |
34420 KB |
Output is correct |
44 |
Correct |
91 ms |
34472 KB |
Output is correct |
45 |
Incorrect |
54 ms |
36768 KB |
Output isn't correct |
46 |
Halted |
0 ms |
0 KB |
- |