답안 #58690 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58690	2018-07-18T21:36:05 Z	ksun48	Wild Boar (JOI18_wild_boar)	C++14	100 / 100	16072 ms	361208 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){
	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.0 / 12.0

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

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	4 ms	484 KB	Output is correct
4	Correct	3 ms	484 KB	Output is correct
5	Correct	3 ms	568 KB	Output is correct
6	Correct	3 ms	568 KB	Output is correct
7	Correct	3 ms	568 KB	Output is correct
8	Correct	0 ms	568 KB	Output is correct
9	Correct	3 ms	568 KB	Output is correct
10	Correct	3 ms	616 KB	Output is correct
11	Correct	3 ms	616 KB	Output is correct
12	Correct	2 ms	616 KB	Output is correct
13	Correct	3 ms	616 KB	Output is correct
14	Correct	3 ms	616 KB	Output is correct
15	Correct	3 ms	616 KB	Output is correct
16	Correct	2 ms	616 KB	Output is correct
17	Correct	3 ms	616 KB	Output is correct
18	Correct	3 ms	620 KB	Output is correct
19	Correct	3 ms	620 KB	Output is correct
20	Correct	3 ms	620 KB	Output is correct
21	Correct	3 ms	620 KB	Output is correct
22	Correct	2 ms	620 KB	Output is correct
23	Correct	2 ms	620 KB	Output is correct
24	Correct	3 ms	620 KB	Output is correct
25	Correct	2 ms	620 KB	Output is correct
26	Correct	7 ms	620 KB	Output is correct
27	Correct	127 ms	21228 KB	Output is correct
28	Correct	124 ms	21228 KB	Output is correct
29	Correct	474 ms	30236 KB	Output is correct
30	Correct	420 ms	30236 KB	Output is correct
31	Correct	392 ms	30284 KB	Output is correct
32	Correct	406 ms	30284 KB	Output is correct
33	Correct	475 ms	31504 KB	Output is correct
34	Correct	488 ms	31596 KB	Output is correct
35	Correct	390 ms	31616 KB	Output is correct
36	Correct	480 ms	31616 KB	Output is correct
37	Correct	374 ms	31616 KB	Output is correct
38	Correct	499 ms	33228 KB	Output is correct
39	Correct	364 ms	33228 KB	Output is correct
40	Correct	511 ms	33292 KB	Output is correct
41	Correct	514 ms	33292 KB	Output is correct
42	Correct	404 ms	34548 KB	Output is correct
43	Correct	516 ms	35512 KB	Output is correct
44	Correct	455 ms	35528 KB	Output is correct
45	Correct	414 ms	35528 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	4 ms	484 KB	Output is correct
4	Correct	3 ms	484 KB	Output is correct
5	Correct	3 ms	568 KB	Output is correct
6	Correct	3 ms	568 KB	Output is correct
7	Correct	3 ms	568 KB	Output is correct
8	Correct	0 ms	568 KB	Output is correct
9	Correct	3 ms	568 KB	Output is correct
10	Correct	3 ms	616 KB	Output is correct
11	Correct	3 ms	616 KB	Output is correct
12	Correct	2 ms	616 KB	Output is correct
13	Correct	3 ms	616 KB	Output is correct
14	Correct	3 ms	616 KB	Output is correct
15	Correct	3 ms	616 KB	Output is correct
16	Correct	2 ms	616 KB	Output is correct
17	Correct	3 ms	616 KB	Output is correct
18	Correct	3 ms	620 KB	Output is correct
19	Correct	3 ms	620 KB	Output is correct
20	Correct	3 ms	620 KB	Output is correct
21	Correct	3 ms	620 KB	Output is correct
22	Correct	2 ms	620 KB	Output is correct
23	Correct	2 ms	620 KB	Output is correct
24	Correct	3 ms	620 KB	Output is correct
25	Correct	2 ms	620 KB	Output is correct
26	Correct	7 ms	620 KB	Output is correct
27	Correct	127 ms	21228 KB	Output is correct
28	Correct	124 ms	21228 KB	Output is correct
29	Correct	474 ms	30236 KB	Output is correct
30	Correct	420 ms	30236 KB	Output is correct
31	Correct	392 ms	30284 KB	Output is correct
32	Correct	406 ms	30284 KB	Output is correct
33	Correct	475 ms	31504 KB	Output is correct
34	Correct	488 ms	31596 KB	Output is correct
35	Correct	390 ms	31616 KB	Output is correct
36	Correct	480 ms	31616 KB	Output is correct
37	Correct	374 ms	31616 KB	Output is correct
38	Correct	499 ms	33228 KB	Output is correct
39	Correct	364 ms	33228 KB	Output is correct
40	Correct	511 ms	33292 KB	Output is correct
41	Correct	514 ms	33292 KB	Output is correct
42	Correct	404 ms	34548 KB	Output is correct
43	Correct	516 ms	35512 KB	Output is correct
44	Correct	455 ms	35528 KB	Output is correct
45	Correct	414 ms	35528 KB	Output is correct
46	Correct	648 ms	35528 KB	Output is correct
47	Correct	7022 ms	54552 KB	Output is correct
48	Correct	8338 ms	91752 KB	Output is correct
49	Correct	9657 ms	130956 KB	Output is correct
50	Correct	9668 ms	130992 KB	Output is correct
51	Correct	9432 ms	131040 KB	Output is correct
52	Correct	13023 ms	131040 KB	Output is correct
53	Correct	12448 ms	131052 KB	Output is correct
54	Correct	12615 ms	131052 KB	Output is correct
55	Correct	10517 ms	131180 KB	Output is correct
56	Correct	10912 ms	152392 KB	Output is correct
57	Correct	10391 ms	175960 KB	Output is correct
58	Correct	11503 ms	201380 KB	Output is correct
59	Correct	12803 ms	228824 KB	Output is correct
60	Correct	12619 ms	258400 KB	Output is correct
61	Correct	14385 ms	289804 KB	Output is correct
62	Correct	13707 ms	323344 KB	Output is correct
63	Correct	14933 ms	358888 KB	Output is correct
64	Correct	11693 ms	358888 KB	Output is correct
65	Correct	10243 ms	358888 KB	Output is correct

Subtask #4
38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	4 ms	484 KB	Output is correct
4	Correct	3 ms	484 KB	Output is correct
5	Correct	3 ms	568 KB	Output is correct
6	Correct	3 ms	568 KB	Output is correct
7	Correct	3 ms	568 KB	Output is correct
8	Correct	0 ms	568 KB	Output is correct
9	Correct	3 ms	568 KB	Output is correct
10	Correct	3 ms	616 KB	Output is correct
11	Correct	3 ms	616 KB	Output is correct
12	Correct	2 ms	616 KB	Output is correct
13	Correct	3 ms	616 KB	Output is correct
14	Correct	3 ms	616 KB	Output is correct
15	Correct	3 ms	616 KB	Output is correct
16	Correct	2 ms	616 KB	Output is correct
17	Correct	3 ms	616 KB	Output is correct
18	Correct	3 ms	620 KB	Output is correct
19	Correct	3 ms	620 KB	Output is correct
20	Correct	3 ms	620 KB	Output is correct
21	Correct	3 ms	620 KB	Output is correct
22	Correct	2 ms	620 KB	Output is correct
23	Correct	2 ms	620 KB	Output is correct
24	Correct	3 ms	620 KB	Output is correct
25	Correct	2 ms	620 KB	Output is correct
26	Correct	7 ms	620 KB	Output is correct
27	Correct	127 ms	21228 KB	Output is correct
28	Correct	124 ms	21228 KB	Output is correct
29	Correct	474 ms	30236 KB	Output is correct
30	Correct	420 ms	30236 KB	Output is correct
31	Correct	392 ms	30284 KB	Output is correct
32	Correct	406 ms	30284 KB	Output is correct
33	Correct	475 ms	31504 KB	Output is correct
34	Correct	488 ms	31596 KB	Output is correct
35	Correct	390 ms	31616 KB	Output is correct
36	Correct	480 ms	31616 KB	Output is correct
37	Correct	374 ms	31616 KB	Output is correct
38	Correct	499 ms	33228 KB	Output is correct
39	Correct	364 ms	33228 KB	Output is correct
40	Correct	511 ms	33292 KB	Output is correct
41	Correct	514 ms	33292 KB	Output is correct
42	Correct	404 ms	34548 KB	Output is correct
43	Correct	516 ms	35512 KB	Output is correct
44	Correct	455 ms	35528 KB	Output is correct
45	Correct	414 ms	35528 KB	Output is correct
46	Correct	648 ms	35528 KB	Output is correct
47	Correct	7022 ms	54552 KB	Output is correct
48	Correct	8338 ms	91752 KB	Output is correct
49	Correct	9657 ms	130956 KB	Output is correct
50	Correct	9668 ms	130992 KB	Output is correct
51	Correct	9432 ms	131040 KB	Output is correct
52	Correct	13023 ms	131040 KB	Output is correct
53	Correct	12448 ms	131052 KB	Output is correct
54	Correct	12615 ms	131052 KB	Output is correct
55	Correct	10517 ms	131180 KB	Output is correct
56	Correct	10912 ms	152392 KB	Output is correct
57	Correct	10391 ms	175960 KB	Output is correct
58	Correct	11503 ms	201380 KB	Output is correct
59	Correct	12803 ms	228824 KB	Output is correct
60	Correct	12619 ms	258400 KB	Output is correct
61	Correct	14385 ms	289804 KB	Output is correct
62	Correct	13707 ms	323344 KB	Output is correct
63	Correct	14933 ms	358888 KB	Output is correct
64	Correct	11693 ms	358888 KB	Output is correct
65	Correct	10243 ms	358888 KB	Output is correct
66	Correct	147 ms	358888 KB	Output is correct
67	Correct	2511 ms	358888 KB	Output is correct
68	Correct	10257 ms	358888 KB	Output is correct
69	Correct	11022 ms	358888 KB	Output is correct
70	Correct	11127 ms	358888 KB	Output is correct
71	Correct	8421 ms	358888 KB	Output is correct
72	Correct	10257 ms	358888 KB	Output is correct
73	Correct	12098 ms	358888 KB	Output is correct
74	Correct	12810 ms	358888 KB	Output is correct
75	Correct	12005 ms	358888 KB	Output is correct
76	Correct	9788 ms	358888 KB	Output is correct
77	Correct	9873 ms	358888 KB	Output is correct
78	Correct	10463 ms	358888 KB	Output is correct
79	Correct	13710 ms	358888 KB	Output is correct
80	Correct	13983 ms	358888 KB	Output is correct
81	Correct	14556 ms	358888 KB	Output is correct
82	Correct	15297 ms	358888 KB	Output is correct
83	Correct	15846 ms	358888 KB	Output is correct
84	Correct	16072 ms	361208 KB	Output is correct
85	Correct	12874 ms	361208 KB	Output is correct

답안 #58690

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 35.0 / 35.0

Subtask #3 15.0 / 15.0

Subtask #4 38.0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
35.0 / 35.0

Subtask #3
15.0 / 15.0

Subtask #4
38.0 / 38.0