답안 #58517 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58517	2018-07-18T04:38:00 Z	ksun48	Wild Boar (JOI18_wild_boar)	C++14	12 / 100	14102 ms	10232 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 < 100; 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	4 ms	248 KB	Output is correct
2	Correct	10 ms	356 KB	Output is correct
3	Correct	11 ms	432 KB	Output is correct
4	Correct	8 ms	432 KB	Output is correct
5	Correct	10 ms	432 KB	Output is correct
6	Correct	7 ms	432 KB	Output is correct
7	Correct	6 ms	512 KB	Output is correct
8	Correct	8 ms	544 KB	Output is correct
9	Correct	13 ms	548 KB	Output is correct
10	Correct	6 ms	548 KB	Output is correct
11	Correct	10 ms	576 KB	Output is correct
12	Correct	12 ms	576 KB	Output is correct
13	Correct	10 ms	624 KB	Output is correct
14	Correct	11 ms	624 KB	Output is correct
15	Correct	10 ms	624 KB	Output is correct
16	Correct	10 ms	624 KB	Output is correct
17	Correct	11 ms	624 KB	Output is correct
18	Correct	13 ms	624 KB	Output is correct
19	Correct	12 ms	624 KB	Output is correct
20	Correct	10 ms	632 KB	Output is correct
21	Correct	7 ms	632 KB	Output is correct
22	Correct	7 ms	632 KB	Output is correct
23	Correct	8 ms	632 KB	Output is correct
24	Correct	7 ms	632 KB	Output is correct
25	Correct	8 ms	632 KB	Output is correct

Subtask #2
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	248 KB	Output is correct
2	Correct	10 ms	356 KB	Output is correct
3	Correct	11 ms	432 KB	Output is correct
4	Correct	8 ms	432 KB	Output is correct
5	Correct	10 ms	432 KB	Output is correct
6	Correct	7 ms	432 KB	Output is correct
7	Correct	6 ms	512 KB	Output is correct
8	Correct	8 ms	544 KB	Output is correct
9	Correct	13 ms	548 KB	Output is correct
10	Correct	6 ms	548 KB	Output is correct
11	Correct	10 ms	576 KB	Output is correct
12	Correct	12 ms	576 KB	Output is correct
13	Correct	10 ms	624 KB	Output is correct
14	Correct	11 ms	624 KB	Output is correct
15	Correct	10 ms	624 KB	Output is correct
16	Correct	10 ms	624 KB	Output is correct
17	Correct	11 ms	624 KB	Output is correct
18	Correct	13 ms	624 KB	Output is correct
19	Correct	12 ms	624 KB	Output is correct
20	Correct	10 ms	632 KB	Output is correct
21	Correct	7 ms	632 KB	Output is correct
22	Correct	7 ms	632 KB	Output is correct
23	Correct	8 ms	632 KB	Output is correct
24	Correct	7 ms	632 KB	Output is correct
25	Correct	8 ms	632 KB	Output is correct
26	Correct	155 ms	748 KB	Output is correct
27	Correct	2057 ms	2240 KB	Output is correct
28	Correct	2161 ms	2268 KB	Output is correct
29	Correct	6511 ms	2356 KB	Output is correct
30	Correct	633 ms	2356 KB	Output is correct
31	Correct	270 ms	2356 KB	Output is correct
32	Correct	335 ms	2356 KB	Output is correct
33	Correct	9175 ms	3500 KB	Output is correct
34	Correct	9651 ms	3500 KB	Output is correct
35	Correct	175 ms	3500 KB	Output is correct
36	Correct	236 ms	3500 KB	Output is correct
37	Correct	9422 ms	3520 KB	Output is correct
38	Correct	10748 ms	5228 KB	Output is correct
39	Correct	339 ms	5228 KB	Output is correct
40	Correct	11759 ms	5228 KB	Output is correct
41	Correct	11243 ms	5228 KB	Output is correct
42	Correct	176 ms	5228 KB	Output is correct
43	Correct	12245 ms	7464 KB	Output is correct
44	Correct	11813 ms	7564 KB	Output is correct
45	Incorrect	14102 ms	10232 KB	Output isn't correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	248 KB	Output is correct
2	Correct	10 ms	356 KB	Output is correct
3	Correct	11 ms	432 KB	Output is correct
4	Correct	8 ms	432 KB	Output is correct
5	Correct	10 ms	432 KB	Output is correct
6	Correct	7 ms	432 KB	Output is correct
7	Correct	6 ms	512 KB	Output is correct
8	Correct	8 ms	544 KB	Output is correct
9	Correct	13 ms	548 KB	Output is correct
10	Correct	6 ms	548 KB	Output is correct
11	Correct	10 ms	576 KB	Output is correct
12	Correct	12 ms	576 KB	Output is correct
13	Correct	10 ms	624 KB	Output is correct
14	Correct	11 ms	624 KB	Output is correct
15	Correct	10 ms	624 KB	Output is correct
16	Correct	10 ms	624 KB	Output is correct
17	Correct	11 ms	624 KB	Output is correct
18	Correct	13 ms	624 KB	Output is correct
19	Correct	12 ms	624 KB	Output is correct
20	Correct	10 ms	632 KB	Output is correct
21	Correct	7 ms	632 KB	Output is correct
22	Correct	7 ms	632 KB	Output is correct
23	Correct	8 ms	632 KB	Output is correct
24	Correct	7 ms	632 KB	Output is correct
25	Correct	8 ms	632 KB	Output is correct
26	Correct	155 ms	748 KB	Output is correct
27	Correct	2057 ms	2240 KB	Output is correct
28	Correct	2161 ms	2268 KB	Output is correct
29	Correct	6511 ms	2356 KB	Output is correct
30	Correct	633 ms	2356 KB	Output is correct
31	Correct	270 ms	2356 KB	Output is correct
32	Correct	335 ms	2356 KB	Output is correct
33	Correct	9175 ms	3500 KB	Output is correct
34	Correct	9651 ms	3500 KB	Output is correct
35	Correct	175 ms	3500 KB	Output is correct
36	Correct	236 ms	3500 KB	Output is correct
37	Correct	9422 ms	3520 KB	Output is correct
38	Correct	10748 ms	5228 KB	Output is correct
39	Correct	339 ms	5228 KB	Output is correct
40	Correct	11759 ms	5228 KB	Output is correct
41	Correct	11243 ms	5228 KB	Output is correct
42	Correct	176 ms	5228 KB	Output is correct
43	Correct	12245 ms	7464 KB	Output is correct
44	Correct	11813 ms	7564 KB	Output is correct
45	Incorrect	14102 ms	10232 KB	Output isn't correct

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	248 KB	Output is correct
2	Correct	10 ms	356 KB	Output is correct
3	Correct	11 ms	432 KB	Output is correct
4	Correct	8 ms	432 KB	Output is correct
5	Correct	10 ms	432 KB	Output is correct
6	Correct	7 ms	432 KB	Output is correct
7	Correct	6 ms	512 KB	Output is correct
8	Correct	8 ms	544 KB	Output is correct
9	Correct	13 ms	548 KB	Output is correct
10	Correct	6 ms	548 KB	Output is correct
11	Correct	10 ms	576 KB	Output is correct
12	Correct	12 ms	576 KB	Output is correct
13	Correct	10 ms	624 KB	Output is correct
14	Correct	11 ms	624 KB	Output is correct
15	Correct	10 ms	624 KB	Output is correct
16	Correct	10 ms	624 KB	Output is correct
17	Correct	11 ms	624 KB	Output is correct
18	Correct	13 ms	624 KB	Output is correct
19	Correct	12 ms	624 KB	Output is correct
20	Correct	10 ms	632 KB	Output is correct
21	Correct	7 ms	632 KB	Output is correct
22	Correct	7 ms	632 KB	Output is correct
23	Correct	8 ms	632 KB	Output is correct
24	Correct	7 ms	632 KB	Output is correct
25	Correct	8 ms	632 KB	Output is correct
26	Correct	155 ms	748 KB	Output is correct
27	Correct	2057 ms	2240 KB	Output is correct
28	Correct	2161 ms	2268 KB	Output is correct
29	Correct	6511 ms	2356 KB	Output is correct
30	Correct	633 ms	2356 KB	Output is correct
31	Correct	270 ms	2356 KB	Output is correct
32	Correct	335 ms	2356 KB	Output is correct
33	Correct	9175 ms	3500 KB	Output is correct
34	Correct	9651 ms	3500 KB	Output is correct
35	Correct	175 ms	3500 KB	Output is correct
36	Correct	236 ms	3500 KB	Output is correct
37	Correct	9422 ms	3520 KB	Output is correct
38	Correct	10748 ms	5228 KB	Output is correct
39	Correct	339 ms	5228 KB	Output is correct
40	Correct	11759 ms	5228 KB	Output is correct
41	Correct	11243 ms	5228 KB	Output is correct
42	Correct	176 ms	5228 KB	Output is correct
43	Correct	12245 ms	7464 KB	Output is correct
44	Correct	11813 ms	7564 KB	Output is correct
45	Incorrect	14102 ms	10232 KB	Output isn't correct

답안 #58517

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