oj.uz

Submission #288271

# Submission time Handle Problem Language Result Execution time Memory
288271 2020-09-01T11:13:37 Z Blagojce Wild Boar (JOI18_wild_boar) C++11
47 / 100
 16918 ms 1048580 KB 
#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,ll> pii;
 
const int i_inf = 1e9;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 2e5+5;
 
const ll A = 911382323;
const ll B = 972663749;

void solve(){
	int n, m, t, len;
	cin >> n >> m >> t >> len;
	vector<pii> g[n];
	int l[m+1], r[m+1];
	fr(i, 0, m){
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		l[i+1] = u, r[i+1] = v;
		g[u].pb({i+1, w});
		g[v].pb({i+1, w});
	}
	int a[len];
	fr(i, 0, len){
		cin >> a[i];
		--a[i];
	}
	
	fr(I, 0, t){
		int p, q;
		cin >> p >> q;
		a[p-1] = q-1;
		
		l[0] = r[0] = a[0];
		
		bool vis[2][m+1][len];
		memset(vis, false, sizeof(vis));
		
		ll dist[2][m+1][len];
		fr(i, 0, 2) fr(j, 0, m+1) fr(k, 0, len) dist[i][j][k] = inf;
		
		
		pq<pair<ll, pair<int,pii> > > Q;
		Q.push({0, {0, {0, 0}}});
		dist[0][0][0] = 0;
		
		while(!Q.empty()){
			int side = Q.top().nd.st;
			int edge = Q.top().nd.nd.st;
			int k = Q.top().nd.nd.nd;
			
			Q.pop();
			if(vis[side][edge][k]) continue;
			vis[side][edge][k] = true;
			
			int u;
			if(side == 0){
				u = l[edge];
			}
			else{
				u = r[edge];
			}
			
			for(auto e : g[u]){
				if(e.st == edge) continue;
				
				int newside, newnode;
				if(u == l[e.st]){
					newnode = r[e.st];
					newside = 1;
				}
				else{
					newnode = l[e.st];
					newside = 0;
				}
				
				int newk = k;
				if(newnode == a[k+1]){
					newk += 1;
				}
				
				if(dist[side][edge][k] + e.nd < dist[newside][e.st][newk]){
					dist[newside][e.st][newk] = dist[side][edge][k] + e.nd;
					Q.push({-dist[newside][e.st][newk], {newside,{e.st, newk}}});
				}
				
				
			}
		}
		ll ans = inf;
		
		for(auto u : g[a[len-1]]){
			int side;
			if(a[len-1] == l[u.st]) side = 0;
			else side = 1;
			ans = min(ans, dist[side][u.st][len-1]);
		}
		
		
		if(ans == inf)cout<<-1<<endl;
		else cout<<ans<<endl;
	}
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tc = 1;
	//cin >> tc;
	while(tc--) solve();
}
/*
5 10 1 10
1 2 8
1 3 5
1 4 2
1 5 1
2 3 7
2 4 9
2 5 6
3 4 10
3 5 10
4 5 6
4
2
4
3
5
3
1
4
3
5
3 5
*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 107 ms 179064 KB Output is correct
28 Correct 107 ms 178936 KB Output is correct
29 Correct 13198 ms 531452 KB Output is correct
30 Correct 14505 ms 531320 KB Output is correct
31 Correct 16251 ms 531324 KB Output is correct
32 Correct 16918 ms 531516 KB Output is correct
33 Correct 12348 ms 531576 KB Output is correct
34 Correct 12393 ms 531456 KB Output is correct
35 Correct 13512 ms 531320 KB Output is correct
36 Correct 13506 ms 531200 KB Output is correct
37 Correct 12370 ms 531468 KB Output is correct
38 Correct 11934 ms 531344 KB Output is correct
39 Correct 12347 ms 531196 KB Output is correct
40 Correct 11801 ms 531344 KB Output is correct
41 Correct 11663 ms 531332 KB Output is correct
42 Correct 10771 ms 531176 KB Output is correct
43 Correct 10665 ms 531448 KB Output is correct
44 Correct 10762 ms 531432 KB Output is correct
45 Correct 4019 ms 531320 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 107 ms 179064 KB Output is correct
28 Correct 107 ms 178936 KB Output is correct
29 Correct 13198 ms 531452 KB Output is correct
30 Correct 14505 ms 531320 KB Output is correct
31 Correct 16251 ms 531324 KB Output is correct
32 Correct 16918 ms 531516 KB Output is correct
33 Correct 12348 ms 531576 KB Output is correct
34 Correct 12393 ms 531456 KB Output is correct
35 Correct 13512 ms 531320 KB Output is correct
36 Correct 13506 ms 531200 KB Output is correct
37 Correct 12370 ms 531468 KB Output is correct
38 Correct 11934 ms 531344 KB Output is correct
39 Correct 12347 ms 531196 KB Output is correct
40 Correct 11801 ms 531344 KB Output is correct
41 Correct 11663 ms 531332 KB Output is correct
42 Correct 10771 ms 531176 KB Output is correct
43 Correct 10665 ms 531448 KB Output is correct
44 Correct 10762 ms 531432 KB Output is correct
45 Correct 4019 ms 531320 KB Output is correct
46 Correct 12 ms 896 KB Output is correct
47 Runtime error 569 ms 1048580 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 107 ms 179064 KB Output is correct
28 Correct 107 ms 178936 KB Output is correct
29 Correct 13198 ms 531452 KB Output is correct
30 Correct 14505 ms 531320 KB Output is correct
31 Correct 16251 ms 531324 KB Output is correct
32 Correct 16918 ms 531516 KB Output is correct
33 Correct 12348 ms 531576 KB Output is correct
34 Correct 12393 ms 531456 KB Output is correct
35 Correct 13512 ms 531320 KB Output is correct
36 Correct 13506 ms 531200 KB Output is correct
37 Correct 12370 ms 531468 KB Output is correct
38 Correct 11934 ms 531344 KB Output is correct
39 Correct 12347 ms 531196 KB Output is correct
40 Correct 11801 ms 531344 KB Output is correct
41 Correct 11663 ms 531332 KB Output is correct
42 Correct 10771 ms 531176 KB Output is correct
43 Correct 10665 ms 531448 KB Output is correct
44 Correct 10762 ms 531432 KB Output is correct
45 Correct 4019 ms 531320 KB Output is correct
46 Correct 12 ms 896 KB Output is correct
47 Runtime error 569 ms 1048580 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -