Submission #58690

#	Time	Username	Problem	Language	Result	Execution time	Memory
58690		ksun48	Wild Boar (JOI18_wild_boar)	C++14	100 / 100	16072 ms	361208 KiB

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;
}

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 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 38 / 38