oj.uz

Submission #524480

# Submission time Handle Problem Language Result Execution time Memory
524480 2022-02-09T09:16:35 Z Koosha_mv Wild Boar (JOI18_wild_boar) C++14
100 / 100
 11333 ms 342748 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 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 5 ms 3020 KB Output is correct
27 Correct 134 ms 63072 KB Output is correct
28 Correct 140 ms 63172 KB Output is correct
29 Correct 298 ms 75868 KB Output is correct
30 Correct 289 ms 75780 KB Output is correct
31 Correct 288 ms 75768 KB Output is correct
32 Correct 295 ms 75824 KB Output is correct
33 Correct 310 ms 76500 KB Output is correct
34 Correct 338 ms 76524 KB Output is correct
35 Correct 280 ms 76464 KB Output is correct
36 Correct 281 ms 76484 KB Output is correct
37 Correct 328 ms 76556 KB Output is correct
38 Correct 317 ms 77364 KB Output is correct
39 Correct 322 ms 77448 KB Output is correct
40 Correct 316 ms 77452 KB Output is correct
41 Correct 341 ms 77468 KB Output is correct
42 Correct 276 ms 78020 KB Output is correct
43 Correct 303 ms 78636 KB Output is correct
44 Correct 310 ms 78504 KB Output is correct
45 Correct 242 ms 79772 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 5 ms 3020 KB Output is correct
27 Correct 134 ms 63072 KB Output is correct
28 Correct 140 ms 63172 KB Output is correct
29 Correct 298 ms 75868 KB Output is correct
30 Correct 289 ms 75780 KB Output is correct
31 Correct 288 ms 75768 KB Output is correct
32 Correct 295 ms 75824 KB Output is correct
33 Correct 310 ms 76500 KB Output is correct
34 Correct 338 ms 76524 KB Output is correct
35 Correct 280 ms 76464 KB Output is correct
36 Correct 281 ms 76484 KB Output is correct
37 Correct 328 ms 76556 KB Output is correct
38 Correct 317 ms 77364 KB Output is correct
39 Correct 322 ms 77448 KB Output is correct
40 Correct 316 ms 77452 KB Output is correct
41 Correct 341 ms 77468 KB Output is correct
42 Correct 276 ms 78020 KB Output is correct
43 Correct 303 ms 78636 KB Output is correct
44 Correct 310 ms 78504 KB Output is correct
45 Correct 242 ms 79772 KB Output is correct
46 Correct 487 ms 34452 KB Output is correct
47 Correct 8236 ms 194716 KB Output is correct
48 Correct 8267 ms 211132 KB Output is correct
49 Correct 8404 ms 226104 KB Output is correct
50 Correct 8434 ms 225988 KB Output is correct
51 Correct 8697 ms 226068 KB Output is correct
52 Correct 8882 ms 226048 KB Output is correct
53 Correct 8806 ms 226040 KB Output is correct
54 Correct 8833 ms 226100 KB Output is correct
55 Correct 8876 ms 226028 KB Output is correct
56 Correct 8844 ms 234708 KB Output is correct
57 Correct 8820 ms 244224 KB Output is correct
58 Correct 8754 ms 254356 KB Output is correct
59 Correct 8702 ms 265360 KB Output is correct
60 Correct 8183 ms 277252 KB Output is correct
61 Correct 7967 ms 289584 KB Output is correct
62 Correct 8005 ms 302888 KB Output is correct
63 Correct 7953 ms 317036 KB Output is correct
64 Correct 4461 ms 341156 KB Output is correct
65 Correct 4536 ms 341116 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 5 ms 3020 KB Output is correct
27 Correct 134 ms 63072 KB Output is correct
28 Correct 140 ms 63172 KB Output is correct
29 Correct 298 ms 75868 KB Output is correct
30 Correct 289 ms 75780 KB Output is correct
31 Correct 288 ms 75768 KB Output is correct
32 Correct 295 ms 75824 KB Output is correct
33 Correct 310 ms 76500 KB Output is correct
34 Correct 338 ms 76524 KB Output is correct
35 Correct 280 ms 76464 KB Output is correct
36 Correct 281 ms 76484 KB Output is correct
37 Correct 328 ms 76556 KB Output is correct
38 Correct 317 ms 77364 KB Output is correct
39 Correct 322 ms 77448 KB Output is correct
40 Correct 316 ms 77452 KB Output is correct
41 Correct 341 ms 77468 KB Output is correct
42 Correct 276 ms 78020 KB Output is correct
43 Correct 303 ms 78636 KB Output is correct
44 Correct 310 ms 78504 KB Output is correct
45 Correct 242 ms 79772 KB Output is correct
46 Correct 487 ms 34452 KB Output is correct
47 Correct 8236 ms 194716 KB Output is correct
48 Correct 8267 ms 211132 KB Output is correct
49 Correct 8404 ms 226104 KB Output is correct
50 Correct 8434 ms 225988 KB Output is correct
51 Correct 8697 ms 226068 KB Output is correct
52 Correct 8882 ms 226048 KB Output is correct
53 Correct 8806 ms 226040 KB Output is correct
54 Correct 8833 ms 226100 KB Output is correct
55 Correct 8876 ms 226028 KB Output is correct
56 Correct 8844 ms 234708 KB Output is correct
57 Correct 8820 ms 244224 KB Output is correct
58 Correct 8754 ms 254356 KB Output is correct
59 Correct 8702 ms 265360 KB Output is correct
60 Correct 8183 ms 277252 KB Output is correct
61 Correct 7967 ms 289584 KB Output is correct
62 Correct 8005 ms 302888 KB Output is correct
63 Correct 7953 ms 317036 KB Output is correct
64 Correct 4461 ms 341156 KB Output is correct
65 Correct 4536 ms 341116 KB Output is correct
66 Correct 144 ms 58692 KB Output is correct
67 Correct 1794 ms 107504 KB Output is correct
68 Correct 4245 ms 285488 KB Output is correct
69 Correct 5009 ms 286008 KB Output is correct
70 Correct 6608 ms 341584 KB Output is correct
71 Correct 10375 ms 196232 KB Output is correct
72 Correct 10506 ms 212756 KB Output is correct
73 Correct 10637 ms 227712 KB Output is correct
74 Correct 11147 ms 227680 KB Output is correct
75 Correct 11333 ms 227712 KB Output is correct
76 Correct 9686 ms 227524 KB Output is correct
77 Correct 9477 ms 227544 KB Output is correct
78 Correct 9559 ms 227504 KB Output is correct
79 Correct 10127 ms 245628 KB Output is correct
80 Correct 10132 ms 255872 KB Output is correct
81 Correct 9720 ms 266668 KB Output is correct
82 Correct 9994 ms 278572 KB Output is correct
83 Correct 9642 ms 291040 KB Output is correct
84 Correct 9798 ms 318492 KB Output is correct
85 Correct 6333 ms 342748 KB Output is correct