oj.uz

Submission #58685

# Submission time Handle Problem Language Result Execution time Memory
58685 2018-07-18T21:07:19 Z ksun48 Wild Boar (JOI18_wild_boar) C++14
62 / 100
 18000 ms 362908 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;
}

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 loc1, OptPaths &q1, int loc2, OptPaths &q2){
	if(v == NULL) return;
	if(v->ridx < loc1 || v->lidx > loc2) return;
	if(v->lidx == v->ridx){
		if(v->lidx == loc1){
			v->paths = q1;
		} else if(v->lidx == loc2){
			v->paths = q2;
		}
	} else {
		upd(v->l, loc1, q1, loc2, q2);
		upd(v->r, loc1, q1, loc2, q2);
		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);
		//cout << "done " << i << endl;
	}

	node * tree = build(0, l - 2);
	for(int i = 0; i <= l-2; i++){
		upd(tree, i, cachedpaths[plan[i]][plan[i+1]], i, cachedpaths[plan[i]][plan[i+1]]);
	}

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 568 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 2 ms 676 KB Output is correct
6 Correct 4 ms 676 KB Output is correct
7 Correct 3 ms 676 KB Output is correct
8 Correct 3 ms 676 KB Output is correct
9 Correct 4 ms 676 KB Output is correct
10 Correct 3 ms 756 KB Output is correct
11 Correct 2 ms 756 KB Output is correct
12 Correct 3 ms 756 KB Output is correct
13 Correct 3 ms 756 KB Output is correct
14 Correct 3 ms 756 KB Output is correct
15 Correct 3 ms 756 KB Output is correct
16 Correct 3 ms 756 KB Output is correct
17 Correct 3 ms 756 KB Output is correct
18 Correct 3 ms 756 KB Output is correct
19 Correct 3 ms 756 KB Output is correct
20 Correct 3 ms 756 KB Output is correct
21 Correct 3 ms 756 KB Output is correct
22 Correct 3 ms 756 KB Output is correct
23 Correct 3 ms 756 KB Output is correct
24 Correct 3 ms 756 KB Output is correct
25 Correct 2 ms 756 KB Output is correct
26 Correct 7 ms 756 KB Output is correct
27 Correct 166 ms 21256 KB Output is correct
28 Correct 168 ms 21296 KB Output is correct
29 Correct 447 ms 30412 KB Output is correct
30 Correct 449 ms 30432 KB Output is correct
31 Correct 389 ms 30432 KB Output is correct
32 Correct 533 ms 30432 KB Output is correct
33 Correct 518 ms 31632 KB Output is correct
34 Correct 479 ms 31632 KB Output is correct
35 Correct 483 ms 31732 KB Output is correct
36 Correct 403 ms 31732 KB Output is correct
37 Correct 458 ms 31732 KB Output is correct
38 Correct 502 ms 33384 KB Output is correct
39 Correct 430 ms 33508 KB Output is correct
40 Correct 471 ms 33508 KB Output is correct
41 Correct 493 ms 33508 KB Output is correct
42 Correct 454 ms 34672 KB Output is correct
43 Correct 500 ms 35648 KB Output is correct
44 Correct 526 ms 35676 KB Output is correct
45 Correct 387 ms 35676 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 568 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 2 ms 676 KB Output is correct
6 Correct 4 ms 676 KB Output is correct
7 Correct 3 ms 676 KB Output is correct
8 Correct 3 ms 676 KB Output is correct
9 Correct 4 ms 676 KB Output is correct
10 Correct 3 ms 756 KB Output is correct
11 Correct 2 ms 756 KB Output is correct
12 Correct 3 ms 756 KB Output is correct
13 Correct 3 ms 756 KB Output is correct
14 Correct 3 ms 756 KB Output is correct
15 Correct 3 ms 756 KB Output is correct
16 Correct 3 ms 756 KB Output is correct
17 Correct 3 ms 756 KB Output is correct
18 Correct 3 ms 756 KB Output is correct
19 Correct 3 ms 756 KB Output is correct
20 Correct 3 ms 756 KB Output is correct
21 Correct 3 ms 756 KB Output is correct
22 Correct 3 ms 756 KB Output is correct
23 Correct 3 ms 756 KB Output is correct
24 Correct 3 ms 756 KB Output is correct
25 Correct 2 ms 756 KB Output is correct
26 Correct 7 ms 756 KB Output is correct
27 Correct 166 ms 21256 KB Output is correct
28 Correct 168 ms 21296 KB Output is correct
29 Correct 447 ms 30412 KB Output is correct
30 Correct 449 ms 30432 KB Output is correct
31 Correct 389 ms 30432 KB Output is correct
32 Correct 533 ms 30432 KB Output is correct
33 Correct 518 ms 31632 KB Output is correct
34 Correct 479 ms 31632 KB Output is correct
35 Correct 483 ms 31732 KB Output is correct
36 Correct 403 ms 31732 KB Output is correct
37 Correct 458 ms 31732 KB Output is correct
38 Correct 502 ms 33384 KB Output is correct
39 Correct 430 ms 33508 KB Output is correct
40 Correct 471 ms 33508 KB Output is correct
41 Correct 493 ms 33508 KB Output is correct
42 Correct 454 ms 34672 KB Output is correct
43 Correct 500 ms 35648 KB Output is correct
44 Correct 526 ms 35676 KB Output is correct
45 Correct 387 ms 35676 KB Output is correct
46 Correct 505 ms 35676 KB Output is correct
47 Correct 6014 ms 54988 KB Output is correct
48 Correct 7204 ms 92140 KB Output is correct
49 Correct 8428 ms 131172 KB Output is correct
50 Correct 8602 ms 131268 KB Output is correct
51 Correct 7591 ms 131268 KB Output is correct
52 Correct 10415 ms 131492 KB Output is correct
53 Correct 10018 ms 131492 KB Output is correct
54 Correct 10161 ms 131492 KB Output is correct
55 Correct 11580 ms 131492 KB Output is correct
56 Correct 12862 ms 152732 KB Output is correct
57 Correct 12213 ms 176064 KB Output is correct
58 Correct 12580 ms 201276 KB Output is correct
59 Correct 13429 ms 228856 KB Output is correct
60 Correct 14935 ms 258364 KB Output is correct
61 Correct 15901 ms 290056 KB Output is correct
62 Correct 16930 ms 323456 KB Output is correct
63 Correct 17708 ms 358996 KB Output is correct
64 Correct 12460 ms 358996 KB Output is correct
65 Correct 11905 ms 358996 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 568 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 2 ms 676 KB Output is correct
6 Correct 4 ms 676 KB Output is correct
7 Correct 3 ms 676 KB Output is correct
8 Correct 3 ms 676 KB Output is correct
9 Correct 4 ms 676 KB Output is correct
10 Correct 3 ms 756 KB Output is correct
11 Correct 2 ms 756 KB Output is correct
12 Correct 3 ms 756 KB Output is correct
13 Correct 3 ms 756 KB Output is correct
14 Correct 3 ms 756 KB Output is correct
15 Correct 3 ms 756 KB Output is correct
16 Correct 3 ms 756 KB Output is correct
17 Correct 3 ms 756 KB Output is correct
18 Correct 3 ms 756 KB Output is correct
19 Correct 3 ms 756 KB Output is correct
20 Correct 3 ms 756 KB Output is correct
21 Correct 3 ms 756 KB Output is correct
22 Correct 3 ms 756 KB Output is correct
23 Correct 3 ms 756 KB Output is correct
24 Correct 3 ms 756 KB Output is correct
25 Correct 2 ms 756 KB Output is correct
26 Correct 7 ms 756 KB Output is correct
27 Correct 166 ms 21256 KB Output is correct
28 Correct 168 ms 21296 KB Output is correct
29 Correct 447 ms 30412 KB Output is correct
30 Correct 449 ms 30432 KB Output is correct
31 Correct 389 ms 30432 KB Output is correct
32 Correct 533 ms 30432 KB Output is correct
33 Correct 518 ms 31632 KB Output is correct
34 Correct 479 ms 31632 KB Output is correct
35 Correct 483 ms 31732 KB Output is correct
36 Correct 403 ms 31732 KB Output is correct
37 Correct 458 ms 31732 KB Output is correct
38 Correct 502 ms 33384 KB Output is correct
39 Correct 430 ms 33508 KB Output is correct
40 Correct 471 ms 33508 KB Output is correct
41 Correct 493 ms 33508 KB Output is correct
42 Correct 454 ms 34672 KB Output is correct
43 Correct 500 ms 35648 KB Output is correct
44 Correct 526 ms 35676 KB Output is correct
45 Correct 387 ms 35676 KB Output is correct
46 Correct 505 ms 35676 KB Output is correct
47 Correct 6014 ms 54988 KB Output is correct
48 Correct 7204 ms 92140 KB Output is correct
49 Correct 8428 ms 131172 KB Output is correct
50 Correct 8602 ms 131268 KB Output is correct
51 Correct 7591 ms 131268 KB Output is correct
52 Correct 10415 ms 131492 KB Output is correct
53 Correct 10018 ms 131492 KB Output is correct
54 Correct 10161 ms 131492 KB Output is correct
55 Correct 11580 ms 131492 KB Output is correct
56 Correct 12862 ms 152732 KB Output is correct
57 Correct 12213 ms 176064 KB Output is correct
58 Correct 12580 ms 201276 KB Output is correct
59 Correct 13429 ms 228856 KB Output is correct
60 Correct 14935 ms 258364 KB Output is correct
61 Correct 15901 ms 290056 KB Output is correct
62 Correct 16930 ms 323456 KB Output is correct
63 Correct 17708 ms 358996 KB Output is correct
64 Correct 12460 ms 358996 KB Output is correct
65 Correct 11905 ms 358996 KB Output is correct
66 Correct 258 ms 358996 KB Output is correct
67 Correct 2680 ms 358996 KB Output is correct
68 Correct 11784 ms 358996 KB Output is correct
69 Correct 11976 ms 358996 KB Output is correct
70 Correct 13675 ms 358996 KB Output is correct
71 Correct 8665 ms 358996 KB Output is correct
72 Correct 9622 ms 358996 KB Output is correct
73 Correct 11801 ms 358996 KB Output is correct
74 Correct 12888 ms 358996 KB Output is correct
75 Correct 13273 ms 358996 KB Output is correct
76 Correct 11019 ms 358996 KB Output is correct
77 Correct 11158 ms 358996 KB Output is correct
78 Correct 11000 ms 358996 KB Output is correct
79 Correct 13576 ms 358996 KB Output is correct
80 Correct 13503 ms 358996 KB Output is correct
81 Correct 13681 ms 358996 KB Output is correct
82 Correct 14758 ms 358996 KB Output is correct
83 Correct 15071 ms 358996 KB Output is correct
84 Execution timed out 18090 ms 362908 KB Time limit exceeded
85 Halted 0 ms 0 KB -