oj.uz

Submission #524461

# Submission time Handle Problem Language Result Execution time Memory
524461 2022-02-09T08:54:12 Z Koosha_mv Wild Boar (JOI18_wild_boar) C++14
100 / 100
 10838 ms 506748 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
#define int ll
 
const int maxn=4040,maxl=500500,S=5,inf=1e18;
 
int n,m,q,L,a[maxl],X[maxn],Y[maxn],cost[maxn],mark[maxn],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(){
	int 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<int,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];
		//cout<<id<<" "<<x<<" : "<<dist[id][x]<<endl;
		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};
			
			//if((u==2 && v==5) || (u==5 && v==1) || (u==1 && v==5) || (u==5 && v==2)){
			/*if(u==5 && v==1){
			cout<<u<<" -> "<<v<<" : "<<endl;
			for(auto p : adj[u][v]){
				cout<<p.F<<" "<<p.S<<" : "<<dist[p.F][p.S]<<endl;
			}
			cout<<endl;
			}*/
		}
	}	
}
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];
			}
		}
		/*cout<<id<<" "<<l<<" "<<r<<" : "<<endl;
		f(i,0,S){
			f(j,0,S){
				cout<<b[l][i].F<<" "<<b[r-1][j].S<<" -> "<<seg[id][i][j]<<endl;
			}
		}*/
		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);
	/*cout<<id<<" "<<l<<" "<<r<<" : "<<endl;
	f(i,0,S){
		f(j,0,S){
			cout<<b[l][i].F<<" "<<b[r-1][j].S<<" -> "<<seg[id][i][j]<<endl;
		}
	}*/
}
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();
	//Get_Ans();
	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];
			}
		}
		//build();
		change(1,0,L-1,x);
		Get_Ans();
	}
}
/*
3 3 1 3
1 2 1
2 3 1
1 3 1
1
2
3
3 1
*/

Compilation message

wild_boar.cpp:192:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  192 | 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 2 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 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 2 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 2 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 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 2 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 136 ms 67824 KB Output is correct
28 Correct 154 ms 67860 KB Output is correct
29 Correct 318 ms 80540 KB Output is correct
30 Correct 296 ms 80580 KB Output is correct
31 Correct 266 ms 80596 KB Output is correct
32 Correct 262 ms 80580 KB Output is correct
33 Correct 365 ms 81720 KB Output is correct
34 Correct 303 ms 81760 KB Output is correct
35 Correct 282 ms 81696 KB Output is correct
36 Correct 279 ms 81732 KB Output is correct
37 Correct 308 ms 81752 KB Output is correct
38 Correct 308 ms 83380 KB Output is correct
39 Correct 275 ms 83308 KB Output is correct
40 Correct 309 ms 83324 KB Output is correct
41 Correct 286 ms 83260 KB Output is correct
42 Correct 257 ms 84476 KB Output is correct
43 Correct 306 ms 85356 KB Output is correct
44 Correct 286 ms 85232 KB Output is correct
45 Correct 218 ms 87596 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 2 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 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 2 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 136 ms 67824 KB Output is correct
28 Correct 154 ms 67860 KB Output is correct
29 Correct 318 ms 80540 KB Output is correct
30 Correct 296 ms 80580 KB Output is correct
31 Correct 266 ms 80596 KB Output is correct
32 Correct 262 ms 80580 KB Output is correct
33 Correct 365 ms 81720 KB Output is correct
34 Correct 303 ms 81760 KB Output is correct
35 Correct 282 ms 81696 KB Output is correct
36 Correct 279 ms 81732 KB Output is correct
37 Correct 308 ms 81752 KB Output is correct
38 Correct 308 ms 83380 KB Output is correct
39 Correct 275 ms 83308 KB Output is correct
40 Correct 309 ms 83324 KB Output is correct
41 Correct 286 ms 83260 KB Output is correct
42 Correct 257 ms 84476 KB Output is correct
43 Correct 306 ms 85356 KB Output is correct
44 Correct 286 ms 85232 KB Output is correct
45 Correct 218 ms 87596 KB Output is correct
46 Correct 461 ms 36128 KB Output is correct
47 Correct 7687 ms 208920 KB Output is correct
48 Correct 7904 ms 240740 KB Output is correct
49 Correct 8157 ms 269696 KB Output is correct
50 Correct 8151 ms 269724 KB Output is correct
51 Correct 8146 ms 269632 KB Output is correct
52 Correct 8492 ms 269672 KB Output is correct
53 Correct 9334 ms 270116 KB Output is correct
54 Correct 10484 ms 270092 KB Output is correct
55 Correct 8914 ms 270072 KB Output is correct
56 Correct 8910 ms 286884 KB Output is correct
57 Correct 9276 ms 305368 KB Output is correct
58 Correct 9017 ms 325296 KB Output is correct
59 Correct 8914 ms 346880 KB Output is correct
60 Correct 8970 ms 369980 KB Output is correct
61 Correct 8934 ms 394600 KB Output is correct
62 Correct 8740 ms 420876 KB Output is correct
63 Correct 8508 ms 448584 KB Output is correct
64 Correct 4913 ms 503908 KB Output is correct
65 Correct 4930 ms 503940 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 2 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 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 2 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 136 ms 67824 KB Output is correct
28 Correct 154 ms 67860 KB Output is correct
29 Correct 318 ms 80540 KB Output is correct
30 Correct 296 ms 80580 KB Output is correct
31 Correct 266 ms 80596 KB Output is correct
32 Correct 262 ms 80580 KB Output is correct
33 Correct 365 ms 81720 KB Output is correct
34 Correct 303 ms 81760 KB Output is correct
35 Correct 282 ms 81696 KB Output is correct
36 Correct 279 ms 81732 KB Output is correct
37 Correct 308 ms 81752 KB Output is correct
38 Correct 308 ms 83380 KB Output is correct
39 Correct 275 ms 83308 KB Output is correct
40 Correct 309 ms 83324 KB Output is correct
41 Correct 286 ms 83260 KB Output is correct
42 Correct 257 ms 84476 KB Output is correct
43 Correct 306 ms 85356 KB Output is correct
44 Correct 286 ms 85232 KB Output is correct
45 Correct 218 ms 87596 KB Output is correct
46 Correct 461 ms 36128 KB Output is correct
47 Correct 7687 ms 208920 KB Output is correct
48 Correct 7904 ms 240740 KB Output is correct
49 Correct 8157 ms 269696 KB Output is correct
50 Correct 8151 ms 269724 KB Output is correct
51 Correct 8146 ms 269632 KB Output is correct
52 Correct 8492 ms 269672 KB Output is correct
53 Correct 9334 ms 270116 KB Output is correct
54 Correct 10484 ms 270092 KB Output is correct
55 Correct 8914 ms 270072 KB Output is correct
56 Correct 8910 ms 286884 KB Output is correct
57 Correct 9276 ms 305368 KB Output is correct
58 Correct 9017 ms 325296 KB Output is correct
59 Correct 8914 ms 346880 KB Output is correct
60 Correct 8970 ms 369980 KB Output is correct
61 Correct 8934 ms 394600 KB Output is correct
62 Correct 8740 ms 420876 KB Output is correct
63 Correct 8508 ms 448584 KB Output is correct
64 Correct 4913 ms 503908 KB Output is correct
65 Correct 4930 ms 503940 KB Output is correct
66 Correct 162 ms 63232 KB Output is correct
67 Correct 1992 ms 147280 KB Output is correct
68 Correct 4640 ms 443680 KB Output is correct
69 Correct 5597 ms 444760 KB Output is correct
70 Correct 6180 ms 504708 KB Output is correct
71 Correct 9741 ms 211344 KB Output is correct
72 Correct 9553 ms 243144 KB Output is correct
73 Correct 10041 ms 272672 KB Output is correct
74 Correct 9982 ms 272696 KB Output is correct
75 Correct 9973 ms 272704 KB Output is correct
76 Correct 9602 ms 272204 KB Output is correct
77 Correct 9613 ms 272148 KB Output is correct
78 Correct 9194 ms 272080 KB Output is correct
79 Correct 10394 ms 307944 KB Output is correct
80 Correct 10503 ms 328004 KB Output is correct
81 Correct 9906 ms 349036 KB Output is correct
82 Correct 10249 ms 372632 KB Output is correct
83 Correct 9779 ms 396732 KB Output is correct
84 Correct 10838 ms 451224 KB Output is correct
85 Correct 6882 ms 506748 KB Output is correct