oj.uz

Submission #787037

# Submission time Handle Problem Language Result Execution time Memory
787037 2023-07-18T16:54:37 Z Ahmed57 Wild Boar (JOI18_wild_boar) C++17
100 / 100
 5448 ms 537880 KB 
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
#define fi first
#define se second
#define pb push_back
int n,m,q,k;
vector<int>adj[2001];
int u[4001],v[4001],w[4001];
int f(int x){return ((x-1)^1)+1;}

ll dis[4001];
int cnt[4001];
bool vis[4001];
priority_queue<pli,vector<pli>,greater<pli> >pq;

struct path{
	int s,e;ll w;
};
path inf={0,0,(ll)1e18};
vector<path>tae[2001][2001];
vector<path>tzu;

void elim(vector<path>&e){
	tzu.clear();tzu.shrink_to_fit();
	for(int i=0; i<5 ;i++){
		path res=inf;
		for(auto newi:e){
			int sx=0,ex=0,px=0;
			for(auto cur:tzu) sx+=(newi.s==cur.s),ex+=(newi.e==cur.e),px+=(newi.s==cur.s && newi.e==cur.e);
			if(sx>=2 || ex>=2 || px>=1) continue;
			if(res.w>newi.w) res=newi;
		}
		tzu.push_back(res);
	}
	e=tzu;
	e.shrink_to_fit();
}
int x[100001];
vector<path>rv[400001];
void pull(int id){
	rv[id].clear();
	for(int i=0; i<5 ;i++){
		for(int j=0; j<5 ;j++){
			if(rv[id*2][i].e!=rv[id*2+1][j].s){
				rv[id].push_back({rv[id*2][i].s,rv[id*2+1][j].e,rv[id*2][i].w+rv[id*2+1][j].w});
			}
		}
	}
	elim(rv[id]);
}
void build(int id,int l,int r){
	if(l+1==r){
		rv[id]=tae[x[l]][x[r]];
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);build(id*2+1,mid,r);
	pull(id);
}
void upd(int id,int l,int r,int y){
	if(r<y || l>y) return;
	if(l+1==r){
		rv[id]=tae[x[l]][x[r]];
		return;
	}
	int mid=(l+r)/2;
	upd(id*2,l,mid,y);upd(id*2+1,mid,r,y);
	pull(id);
}
void out(vector<path>&v){
	for(auto cur:v){
		cout << cur.s << ' ' << cur.e << ' ' << cur.w << endl;
	}
}
int main(){
	ios::sync_with_stdio(false);
	tzu.resize(5);
	cin >> n >> m >> q >> k;
	for(int i=1; i<=m ;i++){
		cin >> u[i*2] >> v[i*2] >> w[i*2];
		u[i*2-1]=v[i*2],v[i*2-1]=u[i*2];w[i*2-1]=w[i*2];
		adj[u[i*2]].push_back(i*2);adj[v[i*2]].push_back(i*2-1);
	}
	for(int i=1; i<=n ;i++){
		for(auto kirino:adj[i]){
			for(int j=1; j<=2*m ;j++) cnt[j]=0,vis[j]=false,dis[j]=1e18;
			dis[kirino]=w[kirino];
			pq.push({dis[kirino],kirino});
			while(!pq.empty()){
				int cur=pq.top().se;pq.pop();
				int id=u[cur];
				if(vis[cur] || cnt[id]>=2) continue;
				vis[cur]=true;cnt[id]++;
				for(auto newi:adj[id]){
					if(cur==newi) continue;
					newi=f(newi);//1 based :(
					if(dis[newi]>dis[cur]+w[newi]){
						dis[newi]=dis[cur]+w[newi];
						pq.push({dis[newi],newi});
					}
				}
			}
			for(int j=1; j<=2*m ;j++){
				tae[v[kirino]][u[j]].push_back({f(kirino),j,dis[j]});
			}
		}
	}
	for(int i=1; i<=n ;i++){
		for(int j=1; j<=n ;j++){
			elim(tae[i][j]);
		}
	}
	for(int i=1; i<=k ;i++) cin >> x[i];
	build(1,1,k);
	for(int i=1; i<=q ;i++){
		int u,v;cin >> u >> v;
		x[u]=v;upd(1,1,k,u);
		ll ans=rv[1][0].w;
		if(ans>=1e18) cout << "-1\n";
		else cout << ans << '\n';
	}

}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 103772 KB Output is correct
2 Correct 46 ms 103732 KB Output is correct
3 Correct 49 ms 103688 KB Output is correct
4 Correct 44 ms 103756 KB Output is correct
5 Correct 45 ms 103720 KB Output is correct
6 Correct 50 ms 104016 KB Output is correct
7 Correct 46 ms 103824 KB Output is correct
8 Correct 45 ms 103808 KB Output is correct
9 Correct 45 ms 103820 KB Output is correct
10 Correct 46 ms 103720 KB Output is correct
11 Correct 45 ms 103812 KB Output is correct
12 Correct 45 ms 103700 KB Output is correct
13 Correct 45 ms 103792 KB Output is correct
14 Correct 48 ms 103876 KB Output is correct
15 Correct 57 ms 103756 KB Output is correct
16 Correct 45 ms 103772 KB Output is correct
17 Correct 46 ms 103720 KB Output is correct
18 Correct 46 ms 103792 KB Output is correct
19 Correct 44 ms 103728 KB Output is correct
20 Correct 47 ms 103892 KB Output is correct
21 Correct 45 ms 103720 KB Output is correct
22 Correct 50 ms 103812 KB Output is correct
23 Correct 46 ms 103808 KB Output is correct
24 Correct 45 ms 103764 KB Output is correct
25 Correct 46 ms 103804 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 103772 KB Output is correct
2 Correct 46 ms 103732 KB Output is correct
3 Correct 49 ms 103688 KB Output is correct
4 Correct 44 ms 103756 KB Output is correct
5 Correct 45 ms 103720 KB Output is correct
6 Correct 50 ms 104016 KB Output is correct
7 Correct 46 ms 103824 KB Output is correct
8 Correct 45 ms 103808 KB Output is correct
9 Correct 45 ms 103820 KB Output is correct
10 Correct 46 ms 103720 KB Output is correct
11 Correct 45 ms 103812 KB Output is correct
12 Correct 45 ms 103700 KB Output is correct
13 Correct 45 ms 103792 KB Output is correct
14 Correct 48 ms 103876 KB Output is correct
15 Correct 57 ms 103756 KB Output is correct
16 Correct 45 ms 103772 KB Output is correct
17 Correct 46 ms 103720 KB Output is correct
18 Correct 46 ms 103792 KB Output is correct
19 Correct 44 ms 103728 KB Output is correct
20 Correct 47 ms 103892 KB Output is correct
21 Correct 45 ms 103720 KB Output is correct
22 Correct 50 ms 103812 KB Output is correct
23 Correct 46 ms 103808 KB Output is correct
24 Correct 45 ms 103764 KB Output is correct
25 Correct 46 ms 103804 KB Output is correct
26 Correct 47 ms 103944 KB Output is correct
27 Correct 109 ms 124268 KB Output is correct
28 Correct 106 ms 124292 KB Output is correct
29 Correct 217 ms 124260 KB Output is correct
30 Correct 213 ms 124188 KB Output is correct
31 Correct 201 ms 124204 KB Output is correct
32 Correct 203 ms 124332 KB Output is correct
33 Correct 215 ms 125644 KB Output is correct
34 Correct 226 ms 125644 KB Output is correct
35 Correct 236 ms 125612 KB Output is correct
36 Correct 210 ms 125596 KB Output is correct
37 Correct 217 ms 125728 KB Output is correct
38 Correct 222 ms 127648 KB Output is correct
39 Correct 208 ms 127408 KB Output is correct
40 Correct 224 ms 127580 KB Output is correct
41 Correct 221 ms 127688 KB Output is correct
42 Correct 203 ms 128772 KB Output is correct
43 Correct 219 ms 129956 KB Output is correct
44 Correct 222 ms 129852 KB Output is correct
45 Correct 179 ms 132044 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 103772 KB Output is correct
2 Correct 46 ms 103732 KB Output is correct
3 Correct 49 ms 103688 KB Output is correct
4 Correct 44 ms 103756 KB Output is correct
5 Correct 45 ms 103720 KB Output is correct
6 Correct 50 ms 104016 KB Output is correct
7 Correct 46 ms 103824 KB Output is correct
8 Correct 45 ms 103808 KB Output is correct
9 Correct 45 ms 103820 KB Output is correct
10 Correct 46 ms 103720 KB Output is correct
11 Correct 45 ms 103812 KB Output is correct
12 Correct 45 ms 103700 KB Output is correct
13 Correct 45 ms 103792 KB Output is correct
14 Correct 48 ms 103876 KB Output is correct
15 Correct 57 ms 103756 KB Output is correct
16 Correct 45 ms 103772 KB Output is correct
17 Correct 46 ms 103720 KB Output is correct
18 Correct 46 ms 103792 KB Output is correct
19 Correct 44 ms 103728 KB Output is correct
20 Correct 47 ms 103892 KB Output is correct
21 Correct 45 ms 103720 KB Output is correct
22 Correct 50 ms 103812 KB Output is correct
23 Correct 46 ms 103808 KB Output is correct
24 Correct 45 ms 103764 KB Output is correct
25 Correct 46 ms 103804 KB Output is correct
26 Correct 47 ms 103944 KB Output is correct
27 Correct 109 ms 124268 KB Output is correct
28 Correct 106 ms 124292 KB Output is correct
29 Correct 217 ms 124260 KB Output is correct
30 Correct 213 ms 124188 KB Output is correct
31 Correct 201 ms 124204 KB Output is correct
32 Correct 203 ms 124332 KB Output is correct
33 Correct 215 ms 125644 KB Output is correct
34 Correct 226 ms 125644 KB Output is correct
35 Correct 236 ms 125612 KB Output is correct
36 Correct 210 ms 125596 KB Output is correct
37 Correct 217 ms 125728 KB Output is correct
38 Correct 222 ms 127648 KB Output is correct
39 Correct 208 ms 127408 KB Output is correct
40 Correct 224 ms 127580 KB Output is correct
41 Correct 221 ms 127688 KB Output is correct
42 Correct 203 ms 128772 KB Output is correct
43 Correct 219 ms 129956 KB Output is correct
44 Correct 222 ms 129852 KB Output is correct
45 Correct 179 ms 132044 KB Output is correct
46 Correct 218 ms 126580 KB Output is correct
47 Correct 2878 ms 432548 KB Output is correct
48 Correct 2942 ms 440640 KB Output is correct
49 Correct 3118 ms 457912 KB Output is correct
50 Correct 3150 ms 446136 KB Output is correct
51 Correct 3159 ms 444944 KB Output is correct
52 Correct 3624 ms 473620 KB Output is correct
53 Correct 3533 ms 477444 KB Output is correct
54 Correct 3611 ms 472892 KB Output is correct
55 Correct 3561 ms 474904 KB Output is correct
56 Correct 3623 ms 477900 KB Output is correct
57 Correct 3672 ms 477600 KB Output is correct
58 Correct 3716 ms 476988 KB Output is correct
59 Correct 3654 ms 482884 KB Output is correct
60 Correct 3801 ms 479588 KB Output is correct
61 Correct 3698 ms 477440 KB Output is correct
62 Correct 3719 ms 469696 KB Output is correct
63 Correct 3723 ms 461552 KB Output is correct
64 Correct 2546 ms 536292 KB Output is correct
65 Correct 2559 ms 536980 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 103772 KB Output is correct
2 Correct 46 ms 103732 KB Output is correct
3 Correct 49 ms 103688 KB Output is correct
4 Correct 44 ms 103756 KB Output is correct
5 Correct 45 ms 103720 KB Output is correct
6 Correct 50 ms 104016 KB Output is correct
7 Correct 46 ms 103824 KB Output is correct
8 Correct 45 ms 103808 KB Output is correct
9 Correct 45 ms 103820 KB Output is correct
10 Correct 46 ms 103720 KB Output is correct
11 Correct 45 ms 103812 KB Output is correct
12 Correct 45 ms 103700 KB Output is correct
13 Correct 45 ms 103792 KB Output is correct
14 Correct 48 ms 103876 KB Output is correct
15 Correct 57 ms 103756 KB Output is correct
16 Correct 45 ms 103772 KB Output is correct
17 Correct 46 ms 103720 KB Output is correct
18 Correct 46 ms 103792 KB Output is correct
19 Correct 44 ms 103728 KB Output is correct
20 Correct 47 ms 103892 KB Output is correct
21 Correct 45 ms 103720 KB Output is correct
22 Correct 50 ms 103812 KB Output is correct
23 Correct 46 ms 103808 KB Output is correct
24 Correct 45 ms 103764 KB Output is correct
25 Correct 46 ms 103804 KB Output is correct
26 Correct 47 ms 103944 KB Output is correct
27 Correct 109 ms 124268 KB Output is correct
28 Correct 106 ms 124292 KB Output is correct
29 Correct 217 ms 124260 KB Output is correct
30 Correct 213 ms 124188 KB Output is correct
31 Correct 201 ms 124204 KB Output is correct
32 Correct 203 ms 124332 KB Output is correct
33 Correct 215 ms 125644 KB Output is correct
34 Correct 226 ms 125644 KB Output is correct
35 Correct 236 ms 125612 KB Output is correct
36 Correct 210 ms 125596 KB Output is correct
37 Correct 217 ms 125728 KB Output is correct
38 Correct 222 ms 127648 KB Output is correct
39 Correct 208 ms 127408 KB Output is correct
40 Correct 224 ms 127580 KB Output is correct
41 Correct 221 ms 127688 KB Output is correct
42 Correct 203 ms 128772 KB Output is correct
43 Correct 219 ms 129956 KB Output is correct
44 Correct 222 ms 129852 KB Output is correct
45 Correct 179 ms 132044 KB Output is correct
46 Correct 218 ms 126580 KB Output is correct
47 Correct 2878 ms 432548 KB Output is correct
48 Correct 2942 ms 440640 KB Output is correct
49 Correct 3118 ms 457912 KB Output is correct
50 Correct 3150 ms 446136 KB Output is correct
51 Correct 3159 ms 444944 KB Output is correct
52 Correct 3624 ms 473620 KB Output is correct
53 Correct 3533 ms 477444 KB Output is correct
54 Correct 3611 ms 472892 KB Output is correct
55 Correct 3561 ms 474904 KB Output is correct
56 Correct 3623 ms 477900 KB Output is correct
57 Correct 3672 ms 477600 KB Output is correct
58 Correct 3716 ms 476988 KB Output is correct
59 Correct 3654 ms 482884 KB Output is correct
60 Correct 3801 ms 479588 KB Output is correct
61 Correct 3698 ms 477440 KB Output is correct
62 Correct 3719 ms 469696 KB Output is correct
63 Correct 3723 ms 461552 KB Output is correct
64 Correct 2546 ms 536292 KB Output is correct
65 Correct 2559 ms 536980 KB Output is correct
66 Correct 173 ms 123212 KB Output is correct
67 Correct 996 ms 206760 KB Output is correct
68 Correct 2548 ms 514120 KB Output is correct
69 Correct 2872 ms 518204 KB Output is correct
70 Correct 3128 ms 534356 KB Output is correct
71 Correct 4368 ms 427220 KB Output is correct
72 Correct 4625 ms 440144 KB Output is correct
73 Correct 5176 ms 475264 KB Output is correct
74 Correct 5111 ms 477300 KB Output is correct
75 Correct 5093 ms 475996 KB Output is correct
76 Correct 4730 ms 454552 KB Output is correct
77 Correct 4785 ms 445284 KB Output is correct
78 Correct 4552 ms 443372 KB Output is correct
79 Correct 5356 ms 482880 KB Output is correct
80 Correct 5227 ms 482396 KB Output is correct
81 Correct 4963 ms 469016 KB Output is correct
82 Correct 5448 ms 484848 KB Output is correct
83 Correct 5167 ms 479480 KB Output is correct
84 Correct 5148 ms 465624 KB Output is correct
85 Correct 3835 ms 537880 KB Output is correct