Submission #58684

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
58684	2018-07-18T20:24:12 Z	ksun48	Wild Boar (JOI18_wild_boar)	C++14	62 / 100	18000 ms	368076 KB

wild_boar

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
 
const LL MAXD = (1LL << 60LL);
int n, m, t, l;
vector<int> a, b;
vector<LL> c;
typedef pair<LL, pair<int,int> > Path;
typedef vector<Path> OptPaths;
int unused = 3000;
 
Path new_unused(){
	Path x = {MAXD, {unused,unused}};
	//unused ++;
	return x;
}
 
Path alt_path(pair<int,int> avoid, OptPaths& paths){
	Path f = new_unused();
	for(Path x : paths){
		if(x.second.first != avoid.first && x.second.second != avoid.second){
			if(x.first < f.first){
				f = x;
			}
		}
	}
	return f;
}
 
Path alt_path2(pair<int,int> avoid, OptPaths& paths){
	Path f = new_unused();
	for(Path x : paths){
		if(x.second.first != avoid.first || x.second.second != avoid.second){
			if(x.first < f.first){
				f = x;
			}
		}
	}
	return f;
}
 
 
int np = 0;
OptPaths process(OptPaths cand){
	np++;
	OptPaths edges;
 
	if(cand.size() == 0) return edges;
 
	edges.push_back(alt_path({-1, -1}, cand));
	pair<int,int> x = edges[0].second;
	if(edges[0].first >= MAXD) return edges;
 
	edges.push_back(alt_path2(x, cand));
	pair<int,int> y = edges[1].second;
	if(edges[1].first >= MAXD) return edges;
 
	if(x.first != y.first && x.second != y.second){
		edges.push_back(alt_path({x.first, y.second}, cand));
		edges.push_back(alt_path({y.first, x.second}, cand));
	} else if(x.first == y.first){
		Path q = alt_path({x.first, -1}, cand);
		edges.push_back(q);
		edges.push_back(alt_path({x.first, q.second.second}, cand));
	} else if(x.second == y.second){
		Path q = alt_path({-1, x.second}, cand);
		edges.push_back(q);
		edges.push_back(alt_path({q.second.first, x.second}, cand));
	}
	sort(edges.begin(), edges.end());
	while(edges.size() > 0 && edges[edges.size() - 1].first >= MAXD) edges.pop_back();
	return edges;
}
 
OptPaths join(OptPaths a, OptPaths b){
	OptPaths cand;
	for(auto x : a){
		for(auto y : b){
			if(x.second.second != y.second.first){
				cand.push_back({min(x.first + y.first, MAXD), {x.second.first, y.second.second}});
			}
		}
	}
	return cand;
}
 
vector<vector<OptPaths> > cachedpaths;
 
void compute_paths2(int s){
	// start bellman-ford at s
	vector<OptPaths> sssp(n);
	for(int id = 0; id < m; id++){
		if(a[id] != s && b[id] != s) continue;
		if(b[id] == s) swap(a[id], b[id]);
		// all paths starting with edge id
 
		int st = b[id];
		vector<vector<int> > adj(n);
		for(int i = 0; i < m; i++){
			if(a[i] != s && b[i] != s){
				adj[a[i]].push_back(i);
				adj[b[i]].push_back(i);
			}
		}
		int vis[n][2];
		pair<LL,int> dist[n][2];
		int changed[n];
		for(int i = 0; i < n; i++){
			changed[i] = 0;
			vis[i][0] = vis[i][1] = 0;
			dist[i][0] = {MAXD, -2};
			dist[i][1] = {MAXD, -1};
		}
		dist[st][0] = {c[id], id};
		dist[st][1] = {MAXD, -1};
		changed[st] = 1;
 
		set<pair<LL,int> > stuff;
		for(int i = 0; i < n; i++){
			if(i != s){
				stuff.insert({dist[i][0].first, (i << 1)});
			}
		}
		while(!stuff.empty()){
			pair<LL,int> x = *stuff.begin();
			stuff.erase(stuff.begin());
			int v = x.second >> 1;
			int idx = x.second & 1;
			vis[v][idx] = 1;
			if(!changed[v]) continue;
			changed[v] = 0;
			for(auto i : adj[v]){
				if(b[i] == v){
					swap(a[i], b[i]);
				}
				int w = b[i];
				if(vis[w][0] && vis[w][1]) continue;
				LL d = 0;
				if(dist[v][0].second != i){
					d = min(MAXD, dist[v][0].first + c[i]);
				} else {
					d = min(MAXD, dist[v][1].first + c[i]);
				}
				for(int j = 0; j < 2; j++){
					if(!vis[w][j]){
						stuff.erase({dist[w][j].first, (w << 1) ^ j});
						break;
					}
				}
				if(dist[w][0].second == i){
					if(d < dist[w][0].first){
						changed[w] = 1;
						dist[w][0] = {d, i};
					}
				} else if(dist[w][1].second == i){
					if(d < dist[w][1].first){
						changed[w] = 1;
						dist[w][1] = {d, i};
					}
				} else if(d < dist[w][1].first){
					changed[w] = 1;
					dist[w][1] = {d, i};
				}
				if(dist[w][0] > dist[w][1]) swap(dist[w][0], dist[w][1]);
				for(int j = 0; j < 2; j++){
					if(!vis[w][j]){
						stuff.insert({dist[w][j].first, (w << 1) ^ j});
						break;
					}
				}
			}
		}
		for(int i = 0; i < n; i++){
			if(i == s) continue;
			sssp[i].push_back({dist[i][0].first,{id,dist[i][0].second}});
			sssp[i].push_back({dist[i][1].first,{id,dist[i][1].second}});
		}
	}
	for(int i = 0; i < n; i++){
		if(i == s) continue;
		sssp[i] = process(sssp[i]);
	}
	cachedpaths[s] = sssp;
}
 
struct node {
	node *l, *r;
	int lidx, ridx;
	OptPaths paths;
};
 
node * build(int l, int r){
	node * f = new node();
	f->lidx = l;
	f->ridx = r;
	if(l == r){
		f->l = f->r = NULL;
	} else {
		int m = (l + r) / 2;
		f->l = build(l, m);
		f->r = build(m + 1, r);
	}
	return f;
}
 
void upd(node * v, int loc, OptPaths q){
	if(v == NULL) return;
	if(v->ridx < loc || v->lidx > loc) return;
	if(v->lidx == v->ridx){
		v->paths = q;
	} else {
		upd(v->l, loc, q);
		upd(v->r, loc, q);
		v->paths = process(join(v->l->paths, v->r->paths));
	}
}
 
int main(){
	cin.sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> t >> l;
	cachedpaths.resize(n);
	a.resize(m); b.resize(m); c.resize(m);
	for(int i = 0; i < m; i++){
		cin >> a[i] >> b[i] >> c[i];
		a[i]--; b[i]--;
	}
	vector<int> plan(l);
	vector<int> need(n, 0);
	for(int i = 0; i < l; i++){
		cin >> plan[i];
		plan[i]--;
		need[plan[i]] = 1;
	}
	vector<pair<int,int> > updates(t);
	for(int i = 0; i < t; i++){
		cin >> updates[i].first >> updates[i].second;
		updates[i].first--; updates[i].second--;
		need[updates[i].second] = 1;
	}	
	for(int i = 0; i < n; i++){
		compute_paths2(i);
	}
 
	node * tree = build(0, l - 2);
	for(int i = 0; i <= l-2; i++){
		upd(tree, i, cachedpaths[plan[i]][plan[i+1]]);
	}
 
	for(int tt = 0; tt < t; tt++){
		int x = updates[tt].first;
		plan[x] = updates[tt].second;
		if(x > 0){
			upd(tree, x-1, cachedpaths[plan[x-1]][plan[x]]);
		}
		if(x <= l-2){
			upd(tree, x, cachedpaths[plan[x]][plan[x+1]]);
		}
		OptPaths route = tree->paths;
		cout << (route.size() > 0 && route[0].first < MAXD ? route[0].first : -1) << '\n';
	}
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	556 KB	Output is correct
4	Correct	3 ms	556 KB	Output is correct
5	Correct	3 ms	576 KB	Output is correct
6	Correct	2 ms	588 KB	Output is correct
7	Correct	3 ms	644 KB	Output is correct
8	Correct	2 ms	644 KB	Output is correct
9	Correct	2 ms	648 KB	Output is correct
10	Correct	3 ms	652 KB	Output is correct
11	Correct	2 ms	656 KB	Output is correct
12	Correct	3 ms	772 KB	Output is correct
13	Correct	4 ms	772 KB	Output is correct
14	Correct	3 ms	772 KB	Output is correct
15	Correct	2 ms	772 KB	Output is correct
16	Correct	2 ms	772 KB	Output is correct
17	Correct	3 ms	772 KB	Output is correct
18	Correct	3 ms	772 KB	Output is correct
19	Correct	4 ms	816 KB	Output is correct
20	Correct	2 ms	816 KB	Output is correct
21	Correct	3 ms	816 KB	Output is correct
22	Correct	3 ms	816 KB	Output is correct
23	Correct	2 ms	816 KB	Output is correct
24	Correct	3 ms	816 KB	Output is correct
25	Correct	2 ms	816 KB	Output is correct

Subtask #2
35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	556 KB	Output is correct
4	Correct	3 ms	556 KB	Output is correct
5	Correct	3 ms	576 KB	Output is correct
6	Correct	2 ms	588 KB	Output is correct
7	Correct	3 ms	644 KB	Output is correct
8	Correct	2 ms	644 KB	Output is correct
9	Correct	2 ms	648 KB	Output is correct
10	Correct	3 ms	652 KB	Output is correct
11	Correct	2 ms	656 KB	Output is correct
12	Correct	3 ms	772 KB	Output is correct
13	Correct	4 ms	772 KB	Output is correct
14	Correct	3 ms	772 KB	Output is correct
15	Correct	2 ms	772 KB	Output is correct
16	Correct	2 ms	772 KB	Output is correct
17	Correct	3 ms	772 KB	Output is correct
18	Correct	3 ms	772 KB	Output is correct
19	Correct	4 ms	816 KB	Output is correct
20	Correct	2 ms	816 KB	Output is correct
21	Correct	3 ms	816 KB	Output is correct
22	Correct	3 ms	816 KB	Output is correct
23	Correct	2 ms	816 KB	Output is correct
24	Correct	3 ms	816 KB	Output is correct
25	Correct	2 ms	816 KB	Output is correct
26	Correct	6 ms	816 KB	Output is correct
27	Correct	314 ms	21636 KB	Output is correct
28	Correct	303 ms	21844 KB	Output is correct
29	Correct	593 ms	31304 KB	Output is correct
30	Correct	585 ms	31556 KB	Output is correct
31	Correct	529 ms	31592 KB	Output is correct
32	Correct	515 ms	31856 KB	Output is correct
33	Correct	662 ms	33524 KB	Output is correct
34	Correct	753 ms	33796 KB	Output is correct
35	Correct	635 ms	33796 KB	Output is correct
36	Correct	544 ms	34092 KB	Output is correct
37	Correct	635 ms	34444 KB	Output is correct
38	Correct	633 ms	36548 KB	Output is correct
39	Correct	624 ms	36804 KB	Output is correct
40	Correct	637 ms	37164 KB	Output is correct
41	Correct	632 ms	37312 KB	Output is correct
42	Correct	606 ms	38944 KB	Output is correct
43	Correct	661 ms	40176 KB	Output is correct
44	Correct	687 ms	40768 KB	Output is correct
45	Correct	533 ms	40768 KB	Output is correct

Subtask #3
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	556 KB	Output is correct
4	Correct	3 ms	556 KB	Output is correct
5	Correct	3 ms	576 KB	Output is correct
6	Correct	2 ms	588 KB	Output is correct
7	Correct	3 ms	644 KB	Output is correct
8	Correct	2 ms	644 KB	Output is correct
9	Correct	2 ms	648 KB	Output is correct
10	Correct	3 ms	652 KB	Output is correct
11	Correct	2 ms	656 KB	Output is correct
12	Correct	3 ms	772 KB	Output is correct
13	Correct	4 ms	772 KB	Output is correct
14	Correct	3 ms	772 KB	Output is correct
15	Correct	2 ms	772 KB	Output is correct
16	Correct	2 ms	772 KB	Output is correct
17	Correct	3 ms	772 KB	Output is correct
18	Correct	3 ms	772 KB	Output is correct
19	Correct	4 ms	816 KB	Output is correct
20	Correct	2 ms	816 KB	Output is correct
21	Correct	3 ms	816 KB	Output is correct
22	Correct	3 ms	816 KB	Output is correct
23	Correct	2 ms	816 KB	Output is correct
24	Correct	3 ms	816 KB	Output is correct
25	Correct	2 ms	816 KB	Output is correct
26	Correct	6 ms	816 KB	Output is correct
27	Correct	314 ms	21636 KB	Output is correct
28	Correct	303 ms	21844 KB	Output is correct
29	Correct	593 ms	31304 KB	Output is correct
30	Correct	585 ms	31556 KB	Output is correct
31	Correct	529 ms	31592 KB	Output is correct
32	Correct	515 ms	31856 KB	Output is correct
33	Correct	662 ms	33524 KB	Output is correct
34	Correct	753 ms	33796 KB	Output is correct
35	Correct	635 ms	33796 KB	Output is correct
36	Correct	544 ms	34092 KB	Output is correct
37	Correct	635 ms	34444 KB	Output is correct
38	Correct	633 ms	36548 KB	Output is correct
39	Correct	624 ms	36804 KB	Output is correct
40	Correct	637 ms	37164 KB	Output is correct
41	Correct	632 ms	37312 KB	Output is correct
42	Correct	606 ms	38944 KB	Output is correct
43	Correct	661 ms	40176 KB	Output is correct
44	Correct	687 ms	40768 KB	Output is correct
45	Correct	533 ms	40768 KB	Output is correct
46	Correct	524 ms	40768 KB	Output is correct
47	Correct	6231 ms	60368 KB	Output is correct
48	Correct	7669 ms	97676 KB	Output is correct
49	Correct	8930 ms	137084 KB	Output is correct
50	Correct	9339 ms	137352 KB	Output is correct
51	Correct	8291 ms	137664 KB	Output is correct
52	Correct	11249 ms	137968 KB	Output is correct
53	Correct	10737 ms	137980 KB	Output is correct
54	Correct	10249 ms	138040 KB	Output is correct
55	Correct	11300 ms	138468 KB	Output is correct
56	Correct	11304 ms	160348 KB	Output is correct
57	Correct	11462 ms	184172 KB	Output is correct
58	Correct	12133 ms	209896 KB	Output is correct
59	Correct	12935 ms	237892 KB	Output is correct
60	Correct	13065 ms	267400 KB	Output is correct
61	Correct	13996 ms	298928 KB	Output is correct
62	Correct	15072 ms	332448 KB	Output is correct
63	Correct	15378 ms	368076 KB	Output is correct
64	Correct	11522 ms	368076 KB	Output is correct
65	Correct	11135 ms	368076 KB	Output is correct

Subtask #4
0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	556 KB	Output is correct
4	Correct	3 ms	556 KB	Output is correct
5	Correct	3 ms	576 KB	Output is correct
6	Correct	2 ms	588 KB	Output is correct
7	Correct	3 ms	644 KB	Output is correct
8	Correct	2 ms	644 KB	Output is correct
9	Correct	2 ms	648 KB	Output is correct
10	Correct	3 ms	652 KB	Output is correct
11	Correct	2 ms	656 KB	Output is correct
12	Correct	3 ms	772 KB	Output is correct
13	Correct	4 ms	772 KB	Output is correct
14	Correct	3 ms	772 KB	Output is correct
15	Correct	2 ms	772 KB	Output is correct
16	Correct	2 ms	772 KB	Output is correct
17	Correct	3 ms	772 KB	Output is correct
18	Correct	3 ms	772 KB	Output is correct
19	Correct	4 ms	816 KB	Output is correct
20	Correct	2 ms	816 KB	Output is correct
21	Correct	3 ms	816 KB	Output is correct
22	Correct	3 ms	816 KB	Output is correct
23	Correct	2 ms	816 KB	Output is correct
24	Correct	3 ms	816 KB	Output is correct
25	Correct	2 ms	816 KB	Output is correct
26	Correct	6 ms	816 KB	Output is correct
27	Correct	314 ms	21636 KB	Output is correct
28	Correct	303 ms	21844 KB	Output is correct
29	Correct	593 ms	31304 KB	Output is correct
30	Correct	585 ms	31556 KB	Output is correct
31	Correct	529 ms	31592 KB	Output is correct
32	Correct	515 ms	31856 KB	Output is correct
33	Correct	662 ms	33524 KB	Output is correct
34	Correct	753 ms	33796 KB	Output is correct
35	Correct	635 ms	33796 KB	Output is correct
36	Correct	544 ms	34092 KB	Output is correct
37	Correct	635 ms	34444 KB	Output is correct
38	Correct	633 ms	36548 KB	Output is correct
39	Correct	624 ms	36804 KB	Output is correct
40	Correct	637 ms	37164 KB	Output is correct
41	Correct	632 ms	37312 KB	Output is correct
42	Correct	606 ms	38944 KB	Output is correct
43	Correct	661 ms	40176 KB	Output is correct
44	Correct	687 ms	40768 KB	Output is correct
45	Correct	533 ms	40768 KB	Output is correct
46	Correct	524 ms	40768 KB	Output is correct
47	Correct	6231 ms	60368 KB	Output is correct
48	Correct	7669 ms	97676 KB	Output is correct
49	Correct	8930 ms	137084 KB	Output is correct
50	Correct	9339 ms	137352 KB	Output is correct
51	Correct	8291 ms	137664 KB	Output is correct
52	Correct	11249 ms	137968 KB	Output is correct
53	Correct	10737 ms	137980 KB	Output is correct
54	Correct	10249 ms	138040 KB	Output is correct
55	Correct	11300 ms	138468 KB	Output is correct
56	Correct	11304 ms	160348 KB	Output is correct
57	Correct	11462 ms	184172 KB	Output is correct
58	Correct	12133 ms	209896 KB	Output is correct
59	Correct	12935 ms	237892 KB	Output is correct
60	Correct	13065 ms	267400 KB	Output is correct
61	Correct	13996 ms	298928 KB	Output is correct
62	Correct	15072 ms	332448 KB	Output is correct
63	Correct	15378 ms	368076 KB	Output is correct
64	Correct	11522 ms	368076 KB	Output is correct
65	Correct	11135 ms	368076 KB	Output is correct
66	Correct	513 ms	368076 KB	Output is correct
67	Correct	2820 ms	368076 KB	Output is correct
68	Correct	10790 ms	368076 KB	Output is correct
69	Correct	11105 ms	368076 KB	Output is correct
70	Correct	11399 ms	368076 KB	Output is correct
71	Correct	10676 ms	368076 KB	Output is correct
72	Correct	12177 ms	368076 KB	Output is correct
73	Correct	14766 ms	368076 KB	Output is correct
74	Correct	14095 ms	368076 KB	Output is correct
75	Correct	14022 ms	368076 KB	Output is correct
76	Correct	12796 ms	368076 KB	Output is correct
77	Correct	13255 ms	368076 KB	Output is correct
78	Correct	14305 ms	368076 KB	Output is correct
79	Correct	14987 ms	368076 KB	Output is correct
80	Correct	16289 ms	368076 KB	Output is correct
81	Correct	15800 ms	368076 KB	Output is correct
82	Correct	17770 ms	368076 KB	Output is correct
83	Execution timed out	18086 ms	368076 KB	Time limit exceeded
84	Halted	0 ms	0 KB	-

Submission #58684

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 35.0 / 35.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
35.0 / 35.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 38.0