oj.uz

Submission #524479

# Submission time Handle Problem Language Result Execution time Memory
524479 2022-02-09T09:14:49 Z Koosha_mv Wild Boar (JOI18_wild_boar) C++14
100 / 100
 11332 ms 342828 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
 
const int maxn=4040,maxl=500500,S=5;
const ll inf=1e18;
 
int n,m,q,L,a[maxl],X[maxn],Y[maxn],cost[maxn],mark[maxn];
ll dist[maxn][maxn],seg[maxl][S][S];
vector<pair<int,int> > g[maxn];
pair<int,int> adj[maxn/2][maxn/2][S],b[maxl][S];
 
void Get_Ans(){
	ll ans=inf;
	f(i,0,S){
		f(j,0,S){
			minm(ans,seg[1][i][j]);
		}
	}
	cout<<(ans==inf ? -1 : ans)<<endl;
}
void dijikastra(int id){
	fill(mark, mark + maxn, 0);
	fill(dist[id], dist[id] + maxn, inf);
 
	dist[id][id] = cost[id];
	
	set<pair<ll,int> > s;
	f(i,0,2*m) s.insert({dist[id][i],i});
	while(s.size()){
		int x = (*s.begin()).S, u = Y[x], last = X[x];
		s.erase(*s.begin());
		if(mark[u] == 2) continue ;
		mark[u]++;
		for(auto v : g[u]){
			if(v.F == last) continue ;
			if(dist[id][x] + cost[v.S] < dist[id][v.S]){
				s.erase({dist[id][v.S],v.S});
				dist[id][v.S] = dist[id][x] + cost[v.S];
				s.insert({dist[id][v.S],v.S});
			}
		}
	}
}
void Make(){
	f(i,0,2*m+1) dist[i][2*m]=dist[2*m][i]=inf;
	dist[2 * m][2 * m]=inf;
	f(i,0,2*m) dijikastra(i);
	f(u,1,n+1){
		f(v,1,n+1){
			if(u == v) continue ;
			int x = 2 * m, y = 2 * m, e = 0, p = 0;
			for(auto adju : g[u]){
				for(auto adjv : g[v]){
					adjv.S ^= 1;
					if(dist[adju.S][adjv.S] < dist[x][y]){
						x = adju.S, y = adjv.S;
					}
				}
			}
			adj[u][v][0] = {x, y};
			
			e = 2 * m, p = 2 * m;
			for(auto adju : g[u]){
				for(auto adjv : g[v]){
					adjv.S ^= 1;
					if(adju.S != x && dist[adju.S][adjv.S] < dist[e][p]){
						e = adju.S, p = adjv.S;
					}
				}
			}
			adj[u][v][1] = {e, p};
			
			e = 2 * m, p = 2 * m;
			for(auto adju : g[u]){
				for(auto adjv : g[v]){
					adjv.S ^= 1;
					if(adju.S != x && adjv.S != adj[u][v][1].S && dist[adju.S][adjv.S] < dist[e][p]){
						e = adju.S, p = adjv.S;
					}
				}
			}
			adj[u][v][2] = {e, p};
			
			e = 2 * m, p = 2 * m;
			for(auto adju : g[u]){
				for(auto adjv : g[v]){
					adjv.S ^= 1;
					if(adjv.S != y && dist[adju.S][adjv.S] < dist[e][p]){
						e = adju.S, p = adjv.S;
					}
				}
			}
			adj[u][v][3] = {e, p};
			
			e = 2 * m, p = 2 * m;
			for(auto adju : g[u]){
				for(auto adjv : g[v]){
					adjv.S ^= 1;
					if(adju.S != adj[u][v][3].F && adjv.S != y && dist[adju.S][adjv.S] < dist[e][p]){
						e = adju.S, p = adjv.S;
					}
				}
			}
			adj[u][v][4] = {e, p};
		}
	}	
}
void merge(int id,int id0,int id1,int l,int mid,int r){
	f(i,0,S) f(j,0,S) seg[id][i][j]=inf;
	f(i,0,S){
		f(j,0,S){
			f(k,0,S){
				f(p,0,S){
					if(b[mid-1][j].S/2!=b[mid][k].F/2){
						minm(seg[id][i][p],seg[id0][i][j]+seg[id1][k][p]);
					}
				}
			}
		}
	}
}
void build(int id=1, int l = 0, int r = L - 1){
	if(l + 1 == r){
		f(i,0,S){
			f(j,0,S){
				seg[id][i][j]=dist[b[l][i].F][b[l][j].S];
			}
		}
		return ;
	}
	int mid = (l + r) >> 1;
	build(id * 2 + 0, l, mid);
	build(id * 2 + 1, mid, r);
	merge(id, id * 2 + 0, id * 2 + 1, l, mid, r);
}
void change(int id,int l,int r,int x){
	if(r<x || x<l) return ;
	if(l+1==r){
		f(i,0,S){
			f(j,0,S){
				seg[id][i][j]=(i==j ? dist[b[l][i].F][b[l][i].S] : inf);
			}
		}
		return ;
	}
	int mid=(l+r)>>1;
	change(id*2+0,l,mid,x);
	change(id*2+1,mid,r,x);
	merge(id, id * 2 + 0, id * 2 + 1, l, mid, r);
}
 
main(){
	cin>>n>>m>>q>>L;
	f(i,0,2*m){
		if((i&1) == 0){
			cin >> X[i] >> Y[i] >> cost[i];
			X[i+1] = Y[i], Y[i+1] = X[i];
			cost[i+1] = cost[i];
		}
		g[X[i]].pb({Y[i], i});
	}
	Make();
	f(i,0,L){
		cin >> a[i];
		if(i > 0){
			f(j,0,S){
				b[i-1][j] = adj[a[i-1]][a[i]][j];
			}
		}
	}
	build();
	f(i,0,q){
		int x,val;
		cin>>x>>val; x--;
		a[x]=val;
		if(x>0){
			f(j,0,S){
				b[x-1][j]=adj[a[x-1]][a[x]][j];
			}
		}
		if(x<L-1){
			f(j,0,S){
				b[x][j]=adj[a[x]][a[x+1]][j];
			}
		}
		change(1,0,L-1,x);
		Get_Ans();
	}
}

Compilation message

wild_boar.cpp:171:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  171 | main(){
      | ^~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 1 ms 1100 KB Output is correct
13 Correct 1 ms 1100 KB Output is correct
14 Correct 1 ms 1100 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 1 ms 1100 KB Output is correct
17 Correct 1 ms 1100 KB Output is correct
18 Correct 1 ms 1100 KB Output is correct
19 Correct 1 ms 1100 KB Output is correct
20 Correct 1 ms 1100 KB Output is correct
21 Correct 1 ms 1100 KB Output is correct
22 Correct 1 ms 1100 KB Output is correct
23 Correct 1 ms 1100 KB Output is correct
24 Correct 1 ms 1100 KB Output is correct
25 Correct 1 ms 1100 KB Output is correct
26 Correct 4 ms 3020 KB Output is correct
27 Correct 129 ms 63092 KB Output is correct
28 Correct 134 ms 63172 KB Output is correct
29 Correct 297 ms 75848 KB Output is correct
30 Correct 274 ms 75840 KB Output is correct
31 Correct 287 ms 75800 KB Output is correct
32 Correct 281 ms 75868 KB Output is correct
33 Correct 331 ms 76548 KB Output is correct
34 Correct 294 ms 76536 KB Output is correct
35 Correct 259 ms 76556 KB Output is correct
36 Correct 268 ms 76584 KB Output is correct
37 Correct 297 ms 76612 KB Output is correct
38 Correct 293 ms 77352 KB Output is correct
39 Correct 274 ms 77400 KB Output is correct
40 Correct 309 ms 77432 KB Output is correct
41 Correct 311 ms 77364 KB Output is correct
42 Correct 289 ms 78080 KB Output is correct
43 Correct 295 ms 78456 KB Output is correct
44 Correct 289 ms 78500 KB Output is correct
45 Correct 233 ms 79812 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 1 ms 1100 KB Output is correct
13 Correct 1 ms 1100 KB Output is correct
14 Correct 1 ms 1100 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 1 ms 1100 KB Output is correct
17 Correct 1 ms 1100 KB Output is correct
18 Correct 1 ms 1100 KB Output is correct
19 Correct 1 ms 1100 KB Output is correct
20 Correct 1 ms 1100 KB Output is correct
21 Correct 1 ms 1100 KB Output is correct
22 Correct 1 ms 1100 KB Output is correct
23 Correct 1 ms 1100 KB Output is correct
24 Correct 1 ms 1100 KB Output is correct
25 Correct 1 ms 1100 KB Output is correct
26 Correct 4 ms 3020 KB Output is correct
27 Correct 129 ms 63092 KB Output is correct
28 Correct 134 ms 63172 KB Output is correct
29 Correct 297 ms 75848 KB Output is correct
30 Correct 274 ms 75840 KB Output is correct
31 Correct 287 ms 75800 KB Output is correct
32 Correct 281 ms 75868 KB Output is correct
33 Correct 331 ms 76548 KB Output is correct
34 Correct 294 ms 76536 KB Output is correct
35 Correct 259 ms 76556 KB Output is correct
36 Correct 268 ms 76584 KB Output is correct
37 Correct 297 ms 76612 KB Output is correct
38 Correct 293 ms 77352 KB Output is correct
39 Correct 274 ms 77400 KB Output is correct
40 Correct 309 ms 77432 KB Output is correct
41 Correct 311 ms 77364 KB Output is correct
42 Correct 289 ms 78080 KB Output is correct
43 Correct 295 ms 78456 KB Output is correct
44 Correct 289 ms 78500 KB Output is correct
45 Correct 233 ms 79812 KB Output is correct
46 Correct 457 ms 34556 KB Output is correct
47 Correct 7650 ms 194736 KB Output is correct
48 Correct 7812 ms 211236 KB Output is correct
49 Correct 8061 ms 226088 KB Output is correct
50 Correct 7925 ms 226104 KB Output is correct
51 Correct 7856 ms 226092 KB Output is correct
52 Correct 8233 ms 226024 KB Output is correct
53 Correct 8394 ms 226056 KB Output is correct
54 Correct 8450 ms 226000 KB Output is correct
55 Correct 8431 ms 226164 KB Output is correct
56 Correct 8341 ms 234656 KB Output is correct
57 Correct 8379 ms 244108 KB Output is correct
58 Correct 8903 ms 254232 KB Output is correct
59 Correct 8793 ms 265288 KB Output is correct
60 Correct 9174 ms 276960 KB Output is correct
61 Correct 8673 ms 289452 KB Output is correct
62 Correct 8700 ms 302860 KB Output is correct
63 Correct 8682 ms 316864 KB Output is correct
64 Correct 5462 ms 341040 KB Output is correct
65 Correct 4968 ms 341032 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 1 ms 1100 KB Output is correct
13 Correct 1 ms 1100 KB Output is correct
14 Correct 1 ms 1100 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 1 ms 1100 KB Output is correct
17 Correct 1 ms 1100 KB Output is correct
18 Correct 1 ms 1100 KB Output is correct
19 Correct 1 ms 1100 KB Output is correct
20 Correct 1 ms 1100 KB Output is correct
21 Correct 1 ms 1100 KB Output is correct
22 Correct 1 ms 1100 KB Output is correct
23 Correct 1 ms 1100 KB Output is correct
24 Correct 1 ms 1100 KB Output is correct
25 Correct 1 ms 1100 KB Output is correct
26 Correct 4 ms 3020 KB Output is correct
27 Correct 129 ms 63092 KB Output is correct
28 Correct 134 ms 63172 KB Output is correct
29 Correct 297 ms 75848 KB Output is correct
30 Correct 274 ms 75840 KB Output is correct
31 Correct 287 ms 75800 KB Output is correct
32 Correct 281 ms 75868 KB Output is correct
33 Correct 331 ms 76548 KB Output is correct
34 Correct 294 ms 76536 KB Output is correct
35 Correct 259 ms 76556 KB Output is correct
36 Correct 268 ms 76584 KB Output is correct
37 Correct 297 ms 76612 KB Output is correct
38 Correct 293 ms 77352 KB Output is correct
39 Correct 274 ms 77400 KB Output is correct
40 Correct 309 ms 77432 KB Output is correct
41 Correct 311 ms 77364 KB Output is correct
42 Correct 289 ms 78080 KB Output is correct
43 Correct 295 ms 78456 KB Output is correct
44 Correct 289 ms 78500 KB Output is correct
45 Correct 233 ms 79812 KB Output is correct
46 Correct 457 ms 34556 KB Output is correct
47 Correct 7650 ms 194736 KB Output is correct
48 Correct 7812 ms 211236 KB Output is correct
49 Correct 8061 ms 226088 KB Output is correct
50 Correct 7925 ms 226104 KB Output is correct
51 Correct 7856 ms 226092 KB Output is correct
52 Correct 8233 ms 226024 KB Output is correct
53 Correct 8394 ms 226056 KB Output is correct
54 Correct 8450 ms 226000 KB Output is correct
55 Correct 8431 ms 226164 KB Output is correct
56 Correct 8341 ms 234656 KB Output is correct
57 Correct 8379 ms 244108 KB Output is correct
58 Correct 8903 ms 254232 KB Output is correct
59 Correct 8793 ms 265288 KB Output is correct
60 Correct 9174 ms 276960 KB Output is correct
61 Correct 8673 ms 289452 KB Output is correct
62 Correct 8700 ms 302860 KB Output is correct
63 Correct 8682 ms 316864 KB Output is correct
64 Correct 5462 ms 341040 KB Output is correct
65 Correct 4968 ms 341032 KB Output is correct
66 Correct 151 ms 58564 KB Output is correct
67 Correct 2031 ms 107516 KB Output is correct
68 Correct 4533 ms 285436 KB Output is correct
69 Correct 5283 ms 285728 KB Output is correct
70 Correct 6240 ms 341360 KB Output is correct
71 Correct 10219 ms 196204 KB Output is correct
72 Correct 10338 ms 212572 KB Output is correct
73 Correct 11332 ms 227828 KB Output is correct
74 Correct 11042 ms 227780 KB Output is correct
75 Correct 10074 ms 227812 KB Output is correct
76 Correct 9618 ms 227672 KB Output is correct
77 Correct 9427 ms 227720 KB Output is correct
78 Correct 9578 ms 227560 KB Output is correct
79 Correct 10288 ms 245804 KB Output is correct
80 Correct 10513 ms 256012 KB Output is correct
81 Correct 10539 ms 266916 KB Output is correct
82 Correct 10944 ms 278696 KB Output is correct
83 Correct 11076 ms 291168 KB Output is correct
84 Correct 10484 ms 318464 KB Output is correct
85 Correct 7506 ms 342828 KB Output is correct