oj.uz

Submission #58498

# Submission time Handle Problem Language Result Execution time Memory
58498 2018-07-18T04:22:14 Z ksun48 Wild Boar (JOI18_wild_boar) C++14
12 / 100
 18000 ms 1360 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){
	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;
	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){
		Path q = new_unused();
		y = q.second;
		edges.push_back(q);
	}

	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}});
	x.push_back(new_unused());
	x.push_back(new_unused());
	return x;
}

OptPaths best_paths(int s, int t){
	assert(s != t);
	// start bellman-ford at s
	OptPaths sssp[n];
	for(int i = 0; i < n; i++){
		unused++;
		sssp[i] = edge(unused-1, MAXD);
	}
	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]);
		}
	}
	for(int j = 0; j < 2 * n + 2; j++){
		for(int i = 0; i < m; i++){
			if(a[i] == s || b[i] == s) continue;
			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());
			sssp[b[i]] = process(x);
		}
		for(int i = 0; i < m; i++){
			if(a[i] == s || b[i] == s) continue;
			OptPaths e = edge(i, c[i]);
			OptPaths x = join(sssp[b[i]], e);
			x.insert(x.end(), sssp[a[i]].begin(), sssp[a[i]].end());
			sssp[a[i]] = process(x);
		}
	}
	return sssp[t];
}

int main(){
	cin.sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> t >> l;
	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[0].first < MAXD ? route[0].first : -1) << '\n';
	}
}

Compilation message

wild_boar.cpp: In function 'OptPaths process(OptPaths)':
wild_boar.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cand.size(); i++){
                 ~~^~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 432 KB Output is correct
4 Correct 7 ms 436 KB Output is correct
5 Correct 6 ms 480 KB Output is correct
6 Correct 5 ms 612 KB Output is correct
7 Correct 7 ms 612 KB Output is correct
8 Correct 6 ms 612 KB Output is correct
9 Correct 7 ms 612 KB Output is correct
10 Correct 7 ms 612 KB Output is correct
11 Correct 11 ms 612 KB Output is correct
12 Correct 10 ms 720 KB Output is correct
13 Correct 8 ms 720 KB Output is correct
14 Correct 10 ms 720 KB Output is correct
15 Correct 9 ms 720 KB Output is correct
16 Correct 13 ms 720 KB Output is correct
17 Correct 8 ms 720 KB Output is correct
18 Correct 12 ms 812 KB Output is correct
19 Correct 9 ms 812 KB Output is correct
20 Correct 11 ms 812 KB Output is correct
21 Correct 5 ms 824 KB Output is correct
22 Correct 6 ms 824 KB Output is correct
23 Correct 6 ms 824 KB Output is correct
24 Correct 6 ms 824 KB Output is correct
25 Correct 6 ms 824 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 432 KB Output is correct
4 Correct 7 ms 436 KB Output is correct
5 Correct 6 ms 480 KB Output is correct
6 Correct 5 ms 612 KB Output is correct
7 Correct 7 ms 612 KB Output is correct
8 Correct 6 ms 612 KB Output is correct
9 Correct 7 ms 612 KB Output is correct
10 Correct 7 ms 612 KB Output is correct
11 Correct 11 ms 612 KB Output is correct
12 Correct 10 ms 720 KB Output is correct
13 Correct 8 ms 720 KB Output is correct
14 Correct 10 ms 720 KB Output is correct
15 Correct 9 ms 720 KB Output is correct
16 Correct 13 ms 720 KB Output is correct
17 Correct 8 ms 720 KB Output is correct
18 Correct 12 ms 812 KB Output is correct
19 Correct 9 ms 812 KB Output is correct
20 Correct 11 ms 812 KB Output is correct
21 Correct 5 ms 824 KB Output is correct
22 Correct 6 ms 824 KB Output is correct
23 Correct 6 ms 824 KB Output is correct
24 Correct 6 ms 824 KB Output is correct
25 Correct 6 ms 824 KB Output is correct
26 Correct 573 ms 824 KB Output is correct
27 Execution timed out 18036 ms 1360 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 432 KB Output is correct
4 Correct 7 ms 436 KB Output is correct
5 Correct 6 ms 480 KB Output is correct
6 Correct 5 ms 612 KB Output is correct
7 Correct 7 ms 612 KB Output is correct
8 Correct 6 ms 612 KB Output is correct
9 Correct 7 ms 612 KB Output is correct
10 Correct 7 ms 612 KB Output is correct
11 Correct 11 ms 612 KB Output is correct
12 Correct 10 ms 720 KB Output is correct
13 Correct 8 ms 720 KB Output is correct
14 Correct 10 ms 720 KB Output is correct
15 Correct 9 ms 720 KB Output is correct
16 Correct 13 ms 720 KB Output is correct
17 Correct 8 ms 720 KB Output is correct
18 Correct 12 ms 812 KB Output is correct
19 Correct 9 ms 812 KB Output is correct
20 Correct 11 ms 812 KB Output is correct
21 Correct 5 ms 824 KB Output is correct
22 Correct 6 ms 824 KB Output is correct
23 Correct 6 ms 824 KB Output is correct
24 Correct 6 ms 824 KB Output is correct
25 Correct 6 ms 824 KB Output is correct
26 Correct 573 ms 824 KB Output is correct
27 Execution timed out 18036 ms 1360 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 432 KB Output is correct
4 Correct 7 ms 436 KB Output is correct
5 Correct 6 ms 480 KB Output is correct
6 Correct 5 ms 612 KB Output is correct
7 Correct 7 ms 612 KB Output is correct
8 Correct 6 ms 612 KB Output is correct
9 Correct 7 ms 612 KB Output is correct
10 Correct 7 ms 612 KB Output is correct
11 Correct 11 ms 612 KB Output is correct
12 Correct 10 ms 720 KB Output is correct
13 Correct 8 ms 720 KB Output is correct
14 Correct 10 ms 720 KB Output is correct
15 Correct 9 ms 720 KB Output is correct
16 Correct 13 ms 720 KB Output is correct
17 Correct 8 ms 720 KB Output is correct
18 Correct 12 ms 812 KB Output is correct
19 Correct 9 ms 812 KB Output is correct
20 Correct 11 ms 812 KB Output is correct
21 Correct 5 ms 824 KB Output is correct
22 Correct 6 ms 824 KB Output is correct
23 Correct 6 ms 824 KB Output is correct
24 Correct 6 ms 824 KB Output is correct
25 Correct 6 ms 824 KB Output is correct
26 Correct 573 ms 824 KB Output is correct
27 Execution timed out 18036 ms 1360 KB Time limit exceeded
28 Halted 0 ms 0 KB -