답안 #58512 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58512	2018-07-18T04:32:36 Z	ksun48	Wild Boar (JOI18_wild_boar)	C++14	12 / 100	18000 ms	4436 KB

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;
	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}});
	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);
		for(int i = 0; i < n; i++){
			sssp[i].push_back(new_unused());
		}
		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);
			}
		}
		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[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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	4 ms	448 KB	Output is correct
3	Correct	3 ms	448 KB	Output is correct
4	Correct	4 ms	544 KB	Output is correct
5	Correct	3 ms	544 KB	Output is correct
6	Correct	3 ms	544 KB	Output is correct
7	Correct	2 ms	544 KB	Output is correct
8	Correct	4 ms	544 KB	Output is correct
9	Correct	4 ms	544 KB	Output is correct
10	Correct	4 ms	544 KB	Output is correct
11	Correct	4 ms	784 KB	Output is correct
12	Correct	4 ms	784 KB	Output is correct
13	Correct	4 ms	784 KB	Output is correct
14	Correct	4 ms	784 KB	Output is correct
15	Correct	4 ms	784 KB	Output is correct
16	Correct	3 ms	784 KB	Output is correct
17	Correct	4 ms	784 KB	Output is correct
18	Correct	5 ms	784 KB	Output is correct
19	Correct	6 ms	784 KB	Output is correct
20	Correct	6 ms	784 KB	Output is correct
21	Correct	4 ms	784 KB	Output is correct
22	Correct	3 ms	784 KB	Output is correct
23	Correct	3 ms	784 KB	Output is correct
24	Correct	3 ms	784 KB	Output is correct
25	Correct	4 ms	784 KB	Output is correct

Subtask #2
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	4 ms	448 KB	Output is correct
3	Correct	3 ms	448 KB	Output is correct
4	Correct	4 ms	544 KB	Output is correct
5	Correct	3 ms	544 KB	Output is correct
6	Correct	3 ms	544 KB	Output is correct
7	Correct	2 ms	544 KB	Output is correct
8	Correct	4 ms	544 KB	Output is correct
9	Correct	4 ms	544 KB	Output is correct
10	Correct	4 ms	544 KB	Output is correct
11	Correct	4 ms	784 KB	Output is correct
12	Correct	4 ms	784 KB	Output is correct
13	Correct	4 ms	784 KB	Output is correct
14	Correct	4 ms	784 KB	Output is correct
15	Correct	4 ms	784 KB	Output is correct
16	Correct	3 ms	784 KB	Output is correct
17	Correct	4 ms	784 KB	Output is correct
18	Correct	5 ms	784 KB	Output is correct
19	Correct	6 ms	784 KB	Output is correct
20	Correct	6 ms	784 KB	Output is correct
21	Correct	4 ms	784 KB	Output is correct
22	Correct	3 ms	784 KB	Output is correct
23	Correct	3 ms	784 KB	Output is correct
24	Correct	3 ms	784 KB	Output is correct
25	Correct	4 ms	784 KB	Output is correct
26	Correct	90 ms	784 KB	Output is correct
27	Correct	3496 ms	2188 KB	Output is correct
28	Correct	3551 ms	2428 KB	Output is correct
29	Correct	12385 ms	2888 KB	Output is correct
30	Correct	1351 ms	2888 KB	Output is correct
31	Correct	455 ms	2888 KB	Output is correct
32	Correct	371 ms	2888 KB	Output is correct
33	Execution timed out	18065 ms	4436 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	4 ms	448 KB	Output is correct
3	Correct	3 ms	448 KB	Output is correct
4	Correct	4 ms	544 KB	Output is correct
5	Correct	3 ms	544 KB	Output is correct
6	Correct	3 ms	544 KB	Output is correct
7	Correct	2 ms	544 KB	Output is correct
8	Correct	4 ms	544 KB	Output is correct
9	Correct	4 ms	544 KB	Output is correct
10	Correct	4 ms	544 KB	Output is correct
11	Correct	4 ms	784 KB	Output is correct
12	Correct	4 ms	784 KB	Output is correct
13	Correct	4 ms	784 KB	Output is correct
14	Correct	4 ms	784 KB	Output is correct
15	Correct	4 ms	784 KB	Output is correct
16	Correct	3 ms	784 KB	Output is correct
17	Correct	4 ms	784 KB	Output is correct
18	Correct	5 ms	784 KB	Output is correct
19	Correct	6 ms	784 KB	Output is correct
20	Correct	6 ms	784 KB	Output is correct
21	Correct	4 ms	784 KB	Output is correct
22	Correct	3 ms	784 KB	Output is correct
23	Correct	3 ms	784 KB	Output is correct
24	Correct	3 ms	784 KB	Output is correct
25	Correct	4 ms	784 KB	Output is correct
26	Correct	90 ms	784 KB	Output is correct
27	Correct	3496 ms	2188 KB	Output is correct
28	Correct	3551 ms	2428 KB	Output is correct
29	Correct	12385 ms	2888 KB	Output is correct
30	Correct	1351 ms	2888 KB	Output is correct
31	Correct	455 ms	2888 KB	Output is correct
32	Correct	371 ms	2888 KB	Output is correct
33	Execution timed out	18065 ms	4436 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	4 ms	448 KB	Output is correct
3	Correct	3 ms	448 KB	Output is correct
4	Correct	4 ms	544 KB	Output is correct
5	Correct	3 ms	544 KB	Output is correct
6	Correct	3 ms	544 KB	Output is correct
7	Correct	2 ms	544 KB	Output is correct
8	Correct	4 ms	544 KB	Output is correct
9	Correct	4 ms	544 KB	Output is correct
10	Correct	4 ms	544 KB	Output is correct
11	Correct	4 ms	784 KB	Output is correct
12	Correct	4 ms	784 KB	Output is correct
13	Correct	4 ms	784 KB	Output is correct
14	Correct	4 ms	784 KB	Output is correct
15	Correct	4 ms	784 KB	Output is correct
16	Correct	3 ms	784 KB	Output is correct
17	Correct	4 ms	784 KB	Output is correct
18	Correct	5 ms	784 KB	Output is correct
19	Correct	6 ms	784 KB	Output is correct
20	Correct	6 ms	784 KB	Output is correct
21	Correct	4 ms	784 KB	Output is correct
22	Correct	3 ms	784 KB	Output is correct
23	Correct	3 ms	784 KB	Output is correct
24	Correct	3 ms	784 KB	Output is correct
25	Correct	4 ms	784 KB	Output is correct
26	Correct	90 ms	784 KB	Output is correct
27	Correct	3496 ms	2188 KB	Output is correct
28	Correct	3551 ms	2428 KB	Output is correct
29	Correct	12385 ms	2888 KB	Output is correct
30	Correct	1351 ms	2888 KB	Output is correct
31	Correct	455 ms	2888 KB	Output is correct
32	Correct	371 ms	2888 KB	Output is correct
33	Execution timed out	18065 ms	4436 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

답안 #58512

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 35.0

Subtask #3 0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 35.0

Subtask #3
0 / 15.0

Subtask #4
0 / 38.0