oj.uz

Submission #58690

# Submission time Handle Problem Language Result Execution time Memory
58690 2018-07-18T21:36:05 Z ksun48 Wild Boar (JOI18_wild_boar) C++14
100 / 100
 16072 ms 361208 KB 
#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;
}

vector<int> plan;

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;
		f->paths = cachedpaths[plan[l]][plan[l+1]];
	} else {
		int m = (l + r) / 2;
		f->l = build(l, m);
		f->r = build(m + 1, r);
		f->paths = process(join(f->l->paths, f->r->paths));
	}
	return f;
}

void upd(node * v, int x){
	if(v == NULL) return;
	if(v->ridx < x-1 || v->lidx > x) return;
	if(v->lidx == v->ridx){
		if(v->lidx == x-1){
			v->paths = cachedpaths[plan[x-1]][plan[x]];
		} else if(v->lidx == x){
			v->paths = cachedpaths[plan[x]][plan[x+1]];
		}
	} else {
		upd(v->l, x);
		upd(v->r, x);
		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]--;
	}
	plan.resize(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);
		//cout << "done " << i << endl;
	}

	node * tree = build(0, l - 2);
	for(int tt = 0; tt < t; tt++){
		int x = updates[tt].first;
		plan[x] = updates[tt].second;
		upd(tree, x);
		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 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 4 ms 484 KB Output is correct
4 Correct 3 ms 484 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 3 ms 568 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 0 ms 568 KB Output is correct
9 Correct 3 ms 568 KB Output is correct
10 Correct 3 ms 616 KB Output is correct
11 Correct 3 ms 616 KB Output is correct
12 Correct 2 ms 616 KB Output is correct
13 Correct 3 ms 616 KB Output is correct
14 Correct 3 ms 616 KB Output is correct
15 Correct 3 ms 616 KB Output is correct
16 Correct 2 ms 616 KB Output is correct
17 Correct 3 ms 616 KB Output is correct
18 Correct 3 ms 620 KB Output is correct
19 Correct 3 ms 620 KB Output is correct
20 Correct 3 ms 620 KB Output is correct
21 Correct 3 ms 620 KB Output is correct
22 Correct 2 ms 620 KB Output is correct
23 Correct 2 ms 620 KB Output is correct
24 Correct 3 ms 620 KB Output is correct
25 Correct 2 ms 620 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 4 ms 484 KB Output is correct
4 Correct 3 ms 484 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 3 ms 568 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 0 ms 568 KB Output is correct
9 Correct 3 ms 568 KB Output is correct
10 Correct 3 ms 616 KB Output is correct
11 Correct 3 ms 616 KB Output is correct
12 Correct 2 ms 616 KB Output is correct
13 Correct 3 ms 616 KB Output is correct
14 Correct 3 ms 616 KB Output is correct
15 Correct 3 ms 616 KB Output is correct
16 Correct 2 ms 616 KB Output is correct
17 Correct 3 ms 616 KB Output is correct
18 Correct 3 ms 620 KB Output is correct
19 Correct 3 ms 620 KB Output is correct
20 Correct 3 ms 620 KB Output is correct
21 Correct 3 ms 620 KB Output is correct
22 Correct 2 ms 620 KB Output is correct
23 Correct 2 ms 620 KB Output is correct
24 Correct 3 ms 620 KB Output is correct
25 Correct 2 ms 620 KB Output is correct
26 Correct 7 ms 620 KB Output is correct
27 Correct 127 ms 21228 KB Output is correct
28 Correct 124 ms 21228 KB Output is correct
29 Correct 474 ms 30236 KB Output is correct
30 Correct 420 ms 30236 KB Output is correct
31 Correct 392 ms 30284 KB Output is correct
32 Correct 406 ms 30284 KB Output is correct
33 Correct 475 ms 31504 KB Output is correct
34 Correct 488 ms 31596 KB Output is correct
35 Correct 390 ms 31616 KB Output is correct
36 Correct 480 ms 31616 KB Output is correct
37 Correct 374 ms 31616 KB Output is correct
38 Correct 499 ms 33228 KB Output is correct
39 Correct 364 ms 33228 KB Output is correct
40 Correct 511 ms 33292 KB Output is correct
41 Correct 514 ms 33292 KB Output is correct
42 Correct 404 ms 34548 KB Output is correct
43 Correct 516 ms 35512 KB Output is correct
44 Correct 455 ms 35528 KB Output is correct
45 Correct 414 ms 35528 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 4 ms 484 KB Output is correct
4 Correct 3 ms 484 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 3 ms 568 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 0 ms 568 KB Output is correct
9 Correct 3 ms 568 KB Output is correct
10 Correct 3 ms 616 KB Output is correct
11 Correct 3 ms 616 KB Output is correct
12 Correct 2 ms 616 KB Output is correct
13 Correct 3 ms 616 KB Output is correct
14 Correct 3 ms 616 KB Output is correct
15 Correct 3 ms 616 KB Output is correct
16 Correct 2 ms 616 KB Output is correct
17 Correct 3 ms 616 KB Output is correct
18 Correct 3 ms 620 KB Output is correct
19 Correct 3 ms 620 KB Output is correct
20 Correct 3 ms 620 KB Output is correct
21 Correct 3 ms 620 KB Output is correct
22 Correct 2 ms 620 KB Output is correct
23 Correct 2 ms 620 KB Output is correct
24 Correct 3 ms 620 KB Output is correct
25 Correct 2 ms 620 KB Output is correct
26 Correct 7 ms 620 KB Output is correct
27 Correct 127 ms 21228 KB Output is correct
28 Correct 124 ms 21228 KB Output is correct
29 Correct 474 ms 30236 KB Output is correct
30 Correct 420 ms 30236 KB Output is correct
31 Correct 392 ms 30284 KB Output is correct
32 Correct 406 ms 30284 KB Output is correct
33 Correct 475 ms 31504 KB Output is correct
34 Correct 488 ms 31596 KB Output is correct
35 Correct 390 ms 31616 KB Output is correct
36 Correct 480 ms 31616 KB Output is correct
37 Correct 374 ms 31616 KB Output is correct
38 Correct 499 ms 33228 KB Output is correct
39 Correct 364 ms 33228 KB Output is correct
40 Correct 511 ms 33292 KB Output is correct
41 Correct 514 ms 33292 KB Output is correct
42 Correct 404 ms 34548 KB Output is correct
43 Correct 516 ms 35512 KB Output is correct
44 Correct 455 ms 35528 KB Output is correct
45 Correct 414 ms 35528 KB Output is correct
46 Correct 648 ms 35528 KB Output is correct
47 Correct 7022 ms 54552 KB Output is correct
48 Correct 8338 ms 91752 KB Output is correct
49 Correct 9657 ms 130956 KB Output is correct
50 Correct 9668 ms 130992 KB Output is correct
51 Correct 9432 ms 131040 KB Output is correct
52 Correct 13023 ms 131040 KB Output is correct
53 Correct 12448 ms 131052 KB Output is correct
54 Correct 12615 ms 131052 KB Output is correct
55 Correct 10517 ms 131180 KB Output is correct
56 Correct 10912 ms 152392 KB Output is correct
57 Correct 10391 ms 175960 KB Output is correct
58 Correct 11503 ms 201380 KB Output is correct
59 Correct 12803 ms 228824 KB Output is correct
60 Correct 12619 ms 258400 KB Output is correct
61 Correct 14385 ms 289804 KB Output is correct
62 Correct 13707 ms 323344 KB Output is correct
63 Correct 14933 ms 358888 KB Output is correct
64 Correct 11693 ms 358888 KB Output is correct
65 Correct 10243 ms 358888 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 4 ms 484 KB Output is correct
4 Correct 3 ms 484 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 3 ms 568 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 0 ms 568 KB Output is correct
9 Correct 3 ms 568 KB Output is correct
10 Correct 3 ms 616 KB Output is correct
11 Correct 3 ms 616 KB Output is correct
12 Correct 2 ms 616 KB Output is correct
13 Correct 3 ms 616 KB Output is correct
14 Correct 3 ms 616 KB Output is correct
15 Correct 3 ms 616 KB Output is correct
16 Correct 2 ms 616 KB Output is correct
17 Correct 3 ms 616 KB Output is correct
18 Correct 3 ms 620 KB Output is correct
19 Correct 3 ms 620 KB Output is correct
20 Correct 3 ms 620 KB Output is correct
21 Correct 3 ms 620 KB Output is correct
22 Correct 2 ms 620 KB Output is correct
23 Correct 2 ms 620 KB Output is correct
24 Correct 3 ms 620 KB Output is correct
25 Correct 2 ms 620 KB Output is correct
26 Correct 7 ms 620 KB Output is correct
27 Correct 127 ms 21228 KB Output is correct
28 Correct 124 ms 21228 KB Output is correct
29 Correct 474 ms 30236 KB Output is correct
30 Correct 420 ms 30236 KB Output is correct
31 Correct 392 ms 30284 KB Output is correct
32 Correct 406 ms 30284 KB Output is correct
33 Correct 475 ms 31504 KB Output is correct
34 Correct 488 ms 31596 KB Output is correct
35 Correct 390 ms 31616 KB Output is correct
36 Correct 480 ms 31616 KB Output is correct
37 Correct 374 ms 31616 KB Output is correct
38 Correct 499 ms 33228 KB Output is correct
39 Correct 364 ms 33228 KB Output is correct
40 Correct 511 ms 33292 KB Output is correct
41 Correct 514 ms 33292 KB Output is correct
42 Correct 404 ms 34548 KB Output is correct
43 Correct 516 ms 35512 KB Output is correct
44 Correct 455 ms 35528 KB Output is correct
45 Correct 414 ms 35528 KB Output is correct
46 Correct 648 ms 35528 KB Output is correct
47 Correct 7022 ms 54552 KB Output is correct
48 Correct 8338 ms 91752 KB Output is correct
49 Correct 9657 ms 130956 KB Output is correct
50 Correct 9668 ms 130992 KB Output is correct
51 Correct 9432 ms 131040 KB Output is correct
52 Correct 13023 ms 131040 KB Output is correct
53 Correct 12448 ms 131052 KB Output is correct
54 Correct 12615 ms 131052 KB Output is correct
55 Correct 10517 ms 131180 KB Output is correct
56 Correct 10912 ms 152392 KB Output is correct
57 Correct 10391 ms 175960 KB Output is correct
58 Correct 11503 ms 201380 KB Output is correct
59 Correct 12803 ms 228824 KB Output is correct
60 Correct 12619 ms 258400 KB Output is correct
61 Correct 14385 ms 289804 KB Output is correct
62 Correct 13707 ms 323344 KB Output is correct
63 Correct 14933 ms 358888 KB Output is correct
64 Correct 11693 ms 358888 KB Output is correct
65 Correct 10243 ms 358888 KB Output is correct
66 Correct 147 ms 358888 KB Output is correct
67 Correct 2511 ms 358888 KB Output is correct
68 Correct 10257 ms 358888 KB Output is correct
69 Correct 11022 ms 358888 KB Output is correct
70 Correct 11127 ms 358888 KB Output is correct
71 Correct 8421 ms 358888 KB Output is correct
72 Correct 10257 ms 358888 KB Output is correct
73 Correct 12098 ms 358888 KB Output is correct
74 Correct 12810 ms 358888 KB Output is correct
75 Correct 12005 ms 358888 KB Output is correct
76 Correct 9788 ms 358888 KB Output is correct
77 Correct 9873 ms 358888 KB Output is correct
78 Correct 10463 ms 358888 KB Output is correct
79 Correct 13710 ms 358888 KB Output is correct
80 Correct 13983 ms 358888 KB Output is correct
81 Correct 14556 ms 358888 KB Output is correct
82 Correct 15297 ms 358888 KB Output is correct
83 Correct 15846 ms 358888 KB Output is correct
84 Correct 16072 ms 361208 KB Output is correct
85 Correct 12874 ms 361208 KB Output is correct