Submission #58534

#	Time	Username	Problem	Language	Result	Execution time	Memory
58534		ksun48	Wild Boar (JOI18_wild_boar)	C++14	47 / 100	18073 ms	50492 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){
	for(Path x : paths){
		if(x.second.first == avoid.first) continue;
		if(x.second.second == avoid.second) continue;
		return x;
	}
	return new_unused();
}

OptPaths process(OptPaths cand){
	sort(cand.begin(), cand.end());
	OptPaths edges;
	if(cand.size() == 0) return edges;
	pair<int,int> x = cand[0].second;
	edges.push_back(cand[0]);
	pair<int,int> y;
	for(int i = 0; i < cand.size(); i++){
		if(cand[i].second == x) continue;
		y = cand[i].second;
		edges.push_back(cand[i]);
		break;
	}
	if(edges.size() == 1){
		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());
	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;
}

OptPaths edge(int id, LL cost){
	OptPaths x;
	x.push_back({cost, {id, id}});
	return x;
}

vector<vector<OptPaths> > cachedpaths;
OptPaths best_paths(int s, int t){
	if(cachedpaths[s].empty()){
		// start bellman-ford at s
		vector<OptPaths> sssp(n);
		vector<vector<int> > adj(n); // to, id, cost
		for(int i = 0; i < m; i++){
			if(a[i] == s){
				sssp[b[i]] = edge(i, c[i]);
			} else if(b[i] == s){
				sssp[a[i]] = edge(i, c[i]);
			} else {
				adj[a[i]].push_back(i);
				adj[b[i]].push_back(i);
			}
		}
		int vis[n][4];
		for(int i = 0; i < n; i++){
			for(int j = 0; j < 4; j++){
				vis[i][j] = 0;
			}
		}
		set<pair<LL,pair<int,int> > > stuff;
		for(int i = 0; i < n; i++){
			for(int idx = 0; idx < sssp[i].size(); idx++){
				stuff.insert({sssp[i][idx].first, {i, idx}});
			}
		}
		while(!stuff.empty()){
			pair<LL,pair<int,int> > v = *stuff.begin();
			stuff.erase(stuff.begin());
			vis[v.second.first][v.second.second] = 1;
			for(auto i : adj[v.second.first]){
				if(b[i] == v.second.first){
					swap(a[i], b[i]);
				}
				OptPaths e = edge(i, c[i]);
				OptPaths x = join(sssp[a[i]], e);
				x.insert(x.end(), sssp[b[i]].begin(), sssp[b[i]].end());
				for(int idx = 0; idx < sssp[b[i]].size(); idx++){
					stuff.erase({sssp[b[i]][idx].first, {b[i], idx}});
				}
				sssp[b[i]] = process(x);
				for(int idx = 0; idx < sssp[b[i]].size(); idx++){
					if(!vis[b[i]][idx]){
						stuff.insert({sssp[b[i]][idx].first, {b[i], idx}});
					}
				}
			}
		}
		cachedpaths[s] = sssp;
	}
	return cachedpaths[s][t];
}

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);
	for(int i = 0; i < l; i++){
		cin >> plan[i];
		plan[i]--;
	}
	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--;
	}
	/*for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cout << "paths from " << i << " to " << j << '\n';
			if(i != j){
				OptPaths x = best_paths(i, j);
				for(auto v : x){
					cout << v.second.first << " " << v.second.second << " " << v.first << '\n';
				}
			}
		}
	}*/
	for(int tt = 0; tt < t; tt++){
		plan[updates[tt].first] = updates[tt].second;
		OptPaths route = best_paths(plan[0], plan[1]);
		for(int j = 2; j < l; j++){
			route = process(join(route, best_paths(plan[j-1], plan[j]) ) );
		}
		cout << (route.size() > 0 && route[0].first < MAXD ? route[0].first : -1) << '\n';
	}
}

Compilation message (stderr)

wild_boar.cpp: In function 'OptPaths process(OptPaths)':
wild_boar.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cand.size(); i++){
                 ~~^~~~~~~~~~~~~
wild_boar.cpp: In function 'OptPaths best_paths(int, int)':
wild_boar.cpp:103:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int idx = 0; idx < sssp[i].size(); idx++){
                     ~~~~^~~~~~~~~~~~~~~~
wild_boar.cpp:118:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int idx = 0; idx < sssp[b[i]].size(); idx++){
                      ~~~~^~~~~~~~~~~~~~~~~~~
wild_boar.cpp:122:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int idx = 0; idx < sssp[b[i]].size(); idx++){
                      ~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 35 / 35
• Subtask 3: 0 / 15
• Subtask 4: 0 / 38