oj.uz

Submission #524482

# Submission time Handle Problem Language Result Execution time Memory
524482 2022-02-09T09:19:37 Z Koosha_mv Wild Boar (JOI18_wild_boar) C++14
100 / 100
 10148 ms 342860 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=400400,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 2 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 1036 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 1056 KB Output is correct
12 Correct 1 ms 1040 KB Output is correct
13 Correct 2 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 2 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 1036 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 1056 KB Output is correct
12 Correct 1 ms 1040 KB Output is correct
13 Correct 2 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 3148 KB Output is correct
27 Correct 132 ms 63224 KB Output is correct
28 Correct 165 ms 63344 KB Output is correct
29 Correct 351 ms 75892 KB Output is correct
30 Correct 321 ms 75996 KB Output is correct
31 Correct 306 ms 76100 KB Output is correct
32 Correct 276 ms 75892 KB Output is correct
33 Correct 314 ms 76588 KB Output is correct
34 Correct 315 ms 76608 KB Output is correct
35 Correct 278 ms 76700 KB Output is correct
36 Correct 313 ms 76648 KB Output is correct
37 Correct 329 ms 76748 KB Output is correct
38 Correct 303 ms 77552 KB Output is correct
39 Correct 289 ms 77540 KB Output is correct
40 Correct 321 ms 77572 KB Output is correct
41 Correct 317 ms 77512 KB Output is correct
42 Correct 281 ms 78204 KB Output is correct
43 Correct 304 ms 78720 KB Output is correct
44 Correct 315 ms 78648 KB Output is correct
45 Correct 237 ms 79940 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 2 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 1036 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 1056 KB Output is correct
12 Correct 1 ms 1040 KB Output is correct
13 Correct 2 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 3148 KB Output is correct
27 Correct 132 ms 63224 KB Output is correct
28 Correct 165 ms 63344 KB Output is correct
29 Correct 351 ms 75892 KB Output is correct
30 Correct 321 ms 75996 KB Output is correct
31 Correct 306 ms 76100 KB Output is correct
32 Correct 276 ms 75892 KB Output is correct
33 Correct 314 ms 76588 KB Output is correct
34 Correct 315 ms 76608 KB Output is correct
35 Correct 278 ms 76700 KB Output is correct
36 Correct 313 ms 76648 KB Output is correct
37 Correct 329 ms 76748 KB Output is correct
38 Correct 303 ms 77552 KB Output is correct
39 Correct 289 ms 77540 KB Output is correct
40 Correct 321 ms 77572 KB Output is correct
41 Correct 317 ms 77512 KB Output is correct
42 Correct 281 ms 78204 KB Output is correct
43 Correct 304 ms 78720 KB Output is correct
44 Correct 315 ms 78648 KB Output is correct
45 Correct 237 ms 79940 KB Output is correct
46 Correct 515 ms 34564 KB Output is correct
47 Correct 8309 ms 194752 KB Output is correct
48 Correct 8131 ms 211236 KB Output is correct
49 Correct 9020 ms 226296 KB Output is correct
50 Correct 8223 ms 226148 KB Output is correct
51 Correct 8308 ms 226232 KB Output is correct
52 Correct 8398 ms 226220 KB Output is correct
53 Correct 8300 ms 226360 KB Output is correct
54 Correct 8275 ms 226228 KB Output is correct
55 Correct 8247 ms 226148 KB Output is correct
56 Correct 8323 ms 234776 KB Output is correct
57 Correct 8260 ms 244028 KB Output is correct
58 Correct 8233 ms 254240 KB Output is correct
59 Correct 8211 ms 265164 KB Output is correct
60 Correct 8273 ms 276988 KB Output is correct
61 Correct 8186 ms 289532 KB Output is correct
62 Correct 8060 ms 302784 KB Output is correct
63 Correct 8093 ms 316928 KB Output is correct
64 Correct 4407 ms 340916 KB Output is correct
65 Correct 4369 ms 340932 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 2 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 1036 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 1056 KB Output is correct
12 Correct 1 ms 1040 KB Output is correct
13 Correct 2 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 3148 KB Output is correct
27 Correct 132 ms 63224 KB Output is correct
28 Correct 165 ms 63344 KB Output is correct
29 Correct 351 ms 75892 KB Output is correct
30 Correct 321 ms 75996 KB Output is correct
31 Correct 306 ms 76100 KB Output is correct
32 Correct 276 ms 75892 KB Output is correct
33 Correct 314 ms 76588 KB Output is correct
34 Correct 315 ms 76608 KB Output is correct
35 Correct 278 ms 76700 KB Output is correct
36 Correct 313 ms 76648 KB Output is correct
37 Correct 329 ms 76748 KB Output is correct
38 Correct 303 ms 77552 KB Output is correct
39 Correct 289 ms 77540 KB Output is correct
40 Correct 321 ms 77572 KB Output is correct
41 Correct 317 ms 77512 KB Output is correct
42 Correct 281 ms 78204 KB Output is correct
43 Correct 304 ms 78720 KB Output is correct
44 Correct 315 ms 78648 KB Output is correct
45 Correct 237 ms 79940 KB Output is correct
46 Correct 515 ms 34564 KB Output is correct
47 Correct 8309 ms 194752 KB Output is correct
48 Correct 8131 ms 211236 KB Output is correct
49 Correct 9020 ms 226296 KB Output is correct
50 Correct 8223 ms 226148 KB Output is correct
51 Correct 8308 ms 226232 KB Output is correct
52 Correct 8398 ms 226220 KB Output is correct
53 Correct 8300 ms 226360 KB Output is correct
54 Correct 8275 ms 226228 KB Output is correct
55 Correct 8247 ms 226148 KB Output is correct
56 Correct 8323 ms 234776 KB Output is correct
57 Correct 8260 ms 244028 KB Output is correct
58 Correct 8233 ms 254240 KB Output is correct
59 Correct 8211 ms 265164 KB Output is correct
60 Correct 8273 ms 276988 KB Output is correct
61 Correct 8186 ms 289532 KB Output is correct
62 Correct 8060 ms 302784 KB Output is correct
63 Correct 8093 ms 316928 KB Output is correct
64 Correct 4407 ms 340916 KB Output is correct
65 Correct 4369 ms 340932 KB Output is correct
66 Correct 140 ms 58564 KB Output is correct
67 Correct 1683 ms 107456 KB Output is correct
68 Correct 4022 ms 285456 KB Output is correct
69 Correct 4775 ms 285860 KB Output is correct
70 Correct 5746 ms 341368 KB Output is correct
71 Correct 9269 ms 196084 KB Output is correct
72 Correct 9378 ms 212620 KB Output is correct
73 Correct 9913 ms 227600 KB Output is correct
74 Correct 9890 ms 227708 KB Output is correct
75 Correct 10097 ms 227684 KB Output is correct
76 Correct 9534 ms 227596 KB Output is correct
77 Correct 9231 ms 227724 KB Output is correct
78 Correct 9278 ms 227456 KB Output is correct
79 Correct 10148 ms 245708 KB Output is correct
80 Correct 9950 ms 256000 KB Output is correct
81 Correct 9514 ms 266712 KB Output is correct
82 Correct 9839 ms 278628 KB Output is correct
83 Correct 9300 ms 290936 KB Output is correct
84 Correct 9571 ms 318500 KB Output is correct
85 Correct 6136 ms 342860 KB Output is correct