oj.uz

답안 #524477

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524477 2022-02-09T09:12:56 Z Koosha_mv Wild Boar (JOI18_wild_boar) C++14
100 / 100
 11792 ms 505432 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;
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<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];
		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:172:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  172 | main(){
      | ^~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 3056 KB Output is correct
27 Correct 133 ms 67844 KB Output is correct
28 Correct 129 ms 67788 KB Output is correct
29 Correct 286 ms 80580 KB Output is correct
30 Correct 271 ms 80580 KB Output is correct
31 Correct 256 ms 80580 KB Output is correct
32 Correct 255 ms 80496 KB Output is correct
33 Correct 291 ms 81724 KB Output is correct
34 Correct 314 ms 81692 KB Output is correct
35 Correct 253 ms 81724 KB Output is correct
36 Correct 261 ms 81828 KB Output is correct
37 Correct 289 ms 81744 KB Output is correct
38 Correct 300 ms 83296 KB Output is correct
39 Correct 275 ms 83264 KB Output is correct
40 Correct 286 ms 83428 KB Output is correct
41 Correct 290 ms 83288 KB Output is correct
42 Correct 251 ms 84440 KB Output is correct
43 Correct 283 ms 85256 KB Output is correct
44 Correct 278 ms 85264 KB Output is correct
45 Correct 218 ms 87620 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 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 3056 KB Output is correct
27 Correct 133 ms 67844 KB Output is correct
28 Correct 129 ms 67788 KB Output is correct
29 Correct 286 ms 80580 KB Output is correct
30 Correct 271 ms 80580 KB Output is correct
31 Correct 256 ms 80580 KB Output is correct
32 Correct 255 ms 80496 KB Output is correct
33 Correct 291 ms 81724 KB Output is correct
34 Correct 314 ms 81692 KB Output is correct
35 Correct 253 ms 81724 KB Output is correct
36 Correct 261 ms 81828 KB Output is correct
37 Correct 289 ms 81744 KB Output is correct
38 Correct 300 ms 83296 KB Output is correct
39 Correct 275 ms 83264 KB Output is correct
40 Correct 286 ms 83428 KB Output is correct
41 Correct 290 ms 83288 KB Output is correct
42 Correct 251 ms 84440 KB Output is correct
43 Correct 283 ms 85256 KB Output is correct
44 Correct 278 ms 85264 KB Output is correct
45 Correct 218 ms 87620 KB Output is correct
46 Correct 451 ms 36244 KB Output is correct
47 Correct 7451 ms 208996 KB Output is correct
48 Correct 7482 ms 240648 KB Output is correct
49 Correct 7699 ms 269852 KB Output is correct
50 Correct 7998 ms 269716 KB Output is correct
51 Correct 7659 ms 269684 KB Output is correct
52 Correct 8084 ms 269676 KB Output is correct
53 Correct 8085 ms 269784 KB Output is correct
54 Correct 8118 ms 270068 KB Output is correct
55 Correct 8038 ms 269648 KB Output is correct
56 Correct 8122 ms 286468 KB Output is correct
57 Correct 8135 ms 305008 KB Output is correct
58 Correct 8109 ms 324940 KB Output is correct
59 Correct 8486 ms 346388 KB Output is correct
60 Correct 8604 ms 369576 KB Output is correct
61 Correct 8143 ms 394364 KB Output is correct
62 Correct 8359 ms 420400 KB Output is correct
63 Correct 8082 ms 448144 KB Output is correct
64 Correct 4505 ms 503488 KB Output is correct
65 Correct 4562 ms 503428 KB Output is correct

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 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 3056 KB Output is correct
27 Correct 133 ms 67844 KB Output is correct
28 Correct 129 ms 67788 KB Output is correct
29 Correct 286 ms 80580 KB Output is correct
30 Correct 271 ms 80580 KB Output is correct
31 Correct 256 ms 80580 KB Output is correct
32 Correct 255 ms 80496 KB Output is correct
33 Correct 291 ms 81724 KB Output is correct
34 Correct 314 ms 81692 KB Output is correct
35 Correct 253 ms 81724 KB Output is correct
36 Correct 261 ms 81828 KB Output is correct
37 Correct 289 ms 81744 KB Output is correct
38 Correct 300 ms 83296 KB Output is correct
39 Correct 275 ms 83264 KB Output is correct
40 Correct 286 ms 83428 KB Output is correct
41 Correct 290 ms 83288 KB Output is correct
42 Correct 251 ms 84440 KB Output is correct
43 Correct 283 ms 85256 KB Output is correct
44 Correct 278 ms 85264 KB Output is correct
45 Correct 218 ms 87620 KB Output is correct
46 Correct 451 ms 36244 KB Output is correct
47 Correct 7451 ms 208996 KB Output is correct
48 Correct 7482 ms 240648 KB Output is correct
49 Correct 7699 ms 269852 KB Output is correct
50 Correct 7998 ms 269716 KB Output is correct
51 Correct 7659 ms 269684 KB Output is correct
52 Correct 8084 ms 269676 KB Output is correct
53 Correct 8085 ms 269784 KB Output is correct
54 Correct 8118 ms 270068 KB Output is correct
55 Correct 8038 ms 269648 KB Output is correct
56 Correct 8122 ms 286468 KB Output is correct
57 Correct 8135 ms 305008 KB Output is correct
58 Correct 8109 ms 324940 KB Output is correct
59 Correct 8486 ms 346388 KB Output is correct
60 Correct 8604 ms 369576 KB Output is correct
61 Correct 8143 ms 394364 KB Output is correct
62 Correct 8359 ms 420400 KB Output is correct
63 Correct 8082 ms 448144 KB Output is correct
64 Correct 4505 ms 503488 KB Output is correct
65 Correct 4562 ms 503428 KB Output is correct
66 Correct 139 ms 62896 KB Output is correct
67 Correct 1781 ms 146784 KB Output is correct
68 Correct 4210 ms 443628 KB Output is correct
69 Correct 5161 ms 444124 KB Output is correct
70 Correct 6193 ms 503812 KB Output is correct
71 Correct 9591 ms 210328 KB Output is correct
72 Correct 9852 ms 242272 KB Output is correct
73 Correct 10450 ms 271268 KB Output is correct
74 Correct 10481 ms 271340 KB Output is correct
75 Correct 11156 ms 271348 KB Output is correct
76 Correct 10970 ms 271300 KB Output is correct
77 Correct 10413 ms 271164 KB Output is correct
78 Correct 10109 ms 271140 KB Output is correct
79 Correct 11792 ms 306572 KB Output is correct
80 Correct 11378 ms 326544 KB Output is correct
81 Correct 10346 ms 347964 KB Output is correct
82 Correct 10940 ms 371092 KB Output is correct
83 Correct 10370 ms 395676 KB Output is correct
84 Correct 10947 ms 449920 KB Output is correct
85 Correct 6571 ms 505432 KB Output is correct