oj.uz

Submission #58689

# Submission time Handle Problem Language Result Execution time Memory
58689 2018-07-18T21:33:22 Z ksun48 Wild Boar (JOI18_wild_boar) C++14
47 / 100
 18000 ms 328716 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;
	} else {
		int m = (l + r) / 2;
		f->l = build(l, m);
		f->r = build(m + 1, r);
	}
	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 i = 0; i <= l-1; i += 2){
		upd(tree, i);
	}

	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 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 3 ms 452 KB Output is correct
5 Correct 3 ms 500 KB Output is correct
6 Correct 3 ms 500 KB Output is correct
7 Correct 2 ms 548 KB Output is correct
8 Correct 3 ms 560 KB Output is correct
9 Correct 3 ms 592 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 2 ms 724 KB Output is correct
17 Correct 2 ms 724 KB Output is correct
18 Correct 2 ms 724 KB Output is correct
19 Correct 2 ms 724 KB Output is correct
20 Correct 2 ms 748 KB Output is correct
21 Correct 2 ms 748 KB Output is correct
22 Correct 2 ms 748 KB Output is correct
23 Correct 2 ms 748 KB Output is correct
24 Correct 3 ms 748 KB Output is correct
25 Correct 3 ms 748 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 2 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 3 ms 452 KB Output is correct
5 Correct 3 ms 500 KB Output is correct
6 Correct 3 ms 500 KB Output is correct
7 Correct 2 ms 548 KB Output is correct
8 Correct 3 ms 560 KB Output is correct
9 Correct 3 ms 592 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 2 ms 724 KB Output is correct
17 Correct 2 ms 724 KB Output is correct
18 Correct 2 ms 724 KB Output is correct
19 Correct 2 ms 724 KB Output is correct
20 Correct 2 ms 748 KB Output is correct
21 Correct 2 ms 748 KB Output is correct
22 Correct 2 ms 748 KB Output is correct
23 Correct 2 ms 748 KB Output is correct
24 Correct 3 ms 748 KB Output is correct
25 Correct 3 ms 748 KB Output is correct
26 Correct 8 ms 748 KB Output is correct
27 Correct 127 ms 21424 KB Output is correct
28 Correct 136 ms 21656 KB Output is correct
29 Correct 386 ms 31068 KB Output is correct
30 Correct 370 ms 31068 KB Output is correct
31 Correct 322 ms 31108 KB Output is correct
32 Correct 323 ms 31108 KB Output is correct
33 Correct 408 ms 32384 KB Output is correct
34 Correct 456 ms 32384 KB Output is correct
35 Correct 357 ms 32384 KB Output is correct
36 Correct 398 ms 32384 KB Output is correct
37 Correct 479 ms 32384 KB Output is correct
38 Correct 461 ms 34116 KB Output is correct
39 Correct 373 ms 34116 KB Output is correct
40 Correct 435 ms 34116 KB Output is correct
41 Correct 467 ms 34180 KB Output is correct
42 Correct 455 ms 35420 KB Output is correct
43 Correct 466 ms 36348 KB Output is correct
44 Correct 494 ms 36492 KB Output is correct
45 Correct 356 ms 36492 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 3 ms 452 KB Output is correct
5 Correct 3 ms 500 KB Output is correct
6 Correct 3 ms 500 KB Output is correct
7 Correct 2 ms 548 KB Output is correct
8 Correct 3 ms 560 KB Output is correct
9 Correct 3 ms 592 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 2 ms 724 KB Output is correct
17 Correct 2 ms 724 KB Output is correct
18 Correct 2 ms 724 KB Output is correct
19 Correct 2 ms 724 KB Output is correct
20 Correct 2 ms 748 KB Output is correct
21 Correct 2 ms 748 KB Output is correct
22 Correct 2 ms 748 KB Output is correct
23 Correct 2 ms 748 KB Output is correct
24 Correct 3 ms 748 KB Output is correct
25 Correct 3 ms 748 KB Output is correct
26 Correct 8 ms 748 KB Output is correct
27 Correct 127 ms 21424 KB Output is correct
28 Correct 136 ms 21656 KB Output is correct
29 Correct 386 ms 31068 KB Output is correct
30 Correct 370 ms 31068 KB Output is correct
31 Correct 322 ms 31108 KB Output is correct
32 Correct 323 ms 31108 KB Output is correct
33 Correct 408 ms 32384 KB Output is correct
34 Correct 456 ms 32384 KB Output is correct
35 Correct 357 ms 32384 KB Output is correct
36 Correct 398 ms 32384 KB Output is correct
37 Correct 479 ms 32384 KB Output is correct
38 Correct 461 ms 34116 KB Output is correct
39 Correct 373 ms 34116 KB Output is correct
40 Correct 435 ms 34116 KB Output is correct
41 Correct 467 ms 34180 KB Output is correct
42 Correct 455 ms 35420 KB Output is correct
43 Correct 466 ms 36348 KB Output is correct
44 Correct 494 ms 36492 KB Output is correct
45 Correct 356 ms 36492 KB Output is correct
46 Correct 542 ms 36492 KB Output is correct
47 Correct 6664 ms 55480 KB Output is correct
48 Correct 7909 ms 92700 KB Output is correct
49 Correct 10374 ms 132016 KB Output is correct
50 Correct 9975 ms 132016 KB Output is correct
51 Correct 9884 ms 132016 KB Output is correct
52 Correct 12952 ms 132016 KB Output is correct
53 Correct 12304 ms 132412 KB Output is correct
54 Correct 13102 ms 132696 KB Output is correct
55 Correct 13680 ms 132840 KB Output is correct
56 Correct 13643 ms 154136 KB Output is correct
57 Correct 14208 ms 177360 KB Output is correct
58 Correct 14379 ms 202812 KB Output is correct
59 Correct 15977 ms 230376 KB Output is correct
60 Correct 15711 ms 259888 KB Output is correct
61 Correct 16032 ms 291832 KB Output is correct
62 Correct 16611 ms 325400 KB Output is correct
63 Execution timed out 18092 ms 328716 KB Time limit exceeded
64 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 3 ms 452 KB Output is correct
5 Correct 3 ms 500 KB Output is correct
6 Correct 3 ms 500 KB Output is correct
7 Correct 2 ms 548 KB Output is correct
8 Correct 3 ms 560 KB Output is correct
9 Correct 3 ms 592 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 2 ms 724 KB Output is correct
17 Correct 2 ms 724 KB Output is correct
18 Correct 2 ms 724 KB Output is correct
19 Correct 2 ms 724 KB Output is correct
20 Correct 2 ms 748 KB Output is correct
21 Correct 2 ms 748 KB Output is correct
22 Correct 2 ms 748 KB Output is correct
23 Correct 2 ms 748 KB Output is correct
24 Correct 3 ms 748 KB Output is correct
25 Correct 3 ms 748 KB Output is correct
26 Correct 8 ms 748 KB Output is correct
27 Correct 127 ms 21424 KB Output is correct
28 Correct 136 ms 21656 KB Output is correct
29 Correct 386 ms 31068 KB Output is correct
30 Correct 370 ms 31068 KB Output is correct
31 Correct 322 ms 31108 KB Output is correct
32 Correct 323 ms 31108 KB Output is correct
33 Correct 408 ms 32384 KB Output is correct
34 Correct 456 ms 32384 KB Output is correct
35 Correct 357 ms 32384 KB Output is correct
36 Correct 398 ms 32384 KB Output is correct
37 Correct 479 ms 32384 KB Output is correct
38 Correct 461 ms 34116 KB Output is correct
39 Correct 373 ms 34116 KB Output is correct
40 Correct 435 ms 34116 KB Output is correct
41 Correct 467 ms 34180 KB Output is correct
42 Correct 455 ms 35420 KB Output is correct
43 Correct 466 ms 36348 KB Output is correct
44 Correct 494 ms 36492 KB Output is correct
45 Correct 356 ms 36492 KB Output is correct
46 Correct 542 ms 36492 KB Output is correct
47 Correct 6664 ms 55480 KB Output is correct
48 Correct 7909 ms 92700 KB Output is correct
49 Correct 10374 ms 132016 KB Output is correct
50 Correct 9975 ms 132016 KB Output is correct
51 Correct 9884 ms 132016 KB Output is correct
52 Correct 12952 ms 132016 KB Output is correct
53 Correct 12304 ms 132412 KB Output is correct
54 Correct 13102 ms 132696 KB Output is correct
55 Correct 13680 ms 132840 KB Output is correct
56 Correct 13643 ms 154136 KB Output is correct
57 Correct 14208 ms 177360 KB Output is correct
58 Correct 14379 ms 202812 KB Output is correct
59 Correct 15977 ms 230376 KB Output is correct
60 Correct 15711 ms 259888 KB Output is correct
61 Correct 16032 ms 291832 KB Output is correct
62 Correct 16611 ms 325400 KB Output is correct
63 Execution timed out 18092 ms 328716 KB Time limit exceeded
64 Halted 0 ms 0 KB -