답안 #96216 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96216	2019-02-07T06:26:54 Z	jangwonyoung	Wild Boar (JOI18_wild_boar)	C++14	100 / 100	9040 ms	540664 KB

wild_boar

#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

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	103800 KB	Output is correct
2	Correct	92 ms	103928 KB	Output is correct
3	Correct	98 ms	103772 KB	Output is correct
4	Correct	90 ms	103796 KB	Output is correct
5	Correct	85 ms	103800 KB	Output is correct
6	Correct	88 ms	103788 KB	Output is correct
7	Correct	92 ms	103928 KB	Output is correct
8	Correct	91 ms	103800 KB	Output is correct
9	Correct	91 ms	103816 KB	Output is correct
10	Correct	90 ms	103804 KB	Output is correct
11	Correct	91 ms	103804 KB	Output is correct
12	Correct	94 ms	103984 KB	Output is correct
13	Correct	91 ms	103920 KB	Output is correct
14	Correct	82 ms	103884 KB	Output is correct
15	Correct	80 ms	103800 KB	Output is correct
16	Correct	80 ms	103800 KB	Output is correct
17	Correct	91 ms	103800 KB	Output is correct
18	Correct	95 ms	103800 KB	Output is correct
19	Correct	125 ms	103800 KB	Output is correct
20	Correct	79 ms	103928 KB	Output is correct
21	Correct	79 ms	103800 KB	Output is correct
22	Correct	80 ms	103800 KB	Output is correct
23	Correct	86 ms	103864 KB	Output is correct
24	Correct	93 ms	103800 KB	Output is correct
25	Correct	79 ms	103800 KB	Output is correct

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	103800 KB	Output is correct
2	Correct	92 ms	103928 KB	Output is correct
3	Correct	98 ms	103772 KB	Output is correct
4	Correct	90 ms	103796 KB	Output is correct
5	Correct	85 ms	103800 KB	Output is correct
6	Correct	88 ms	103788 KB	Output is correct
7	Correct	92 ms	103928 KB	Output is correct
8	Correct	91 ms	103800 KB	Output is correct
9	Correct	91 ms	103816 KB	Output is correct
10	Correct	90 ms	103804 KB	Output is correct
11	Correct	91 ms	103804 KB	Output is correct
12	Correct	94 ms	103984 KB	Output is correct
13	Correct	91 ms	103920 KB	Output is correct
14	Correct	82 ms	103884 KB	Output is correct
15	Correct	80 ms	103800 KB	Output is correct
16	Correct	80 ms	103800 KB	Output is correct
17	Correct	91 ms	103800 KB	Output is correct
18	Correct	95 ms	103800 KB	Output is correct
19	Correct	125 ms	103800 KB	Output is correct
20	Correct	79 ms	103928 KB	Output is correct
21	Correct	79 ms	103800 KB	Output is correct
22	Correct	80 ms	103800 KB	Output is correct
23	Correct	86 ms	103864 KB	Output is correct
24	Correct	93 ms	103800 KB	Output is correct
25	Correct	79 ms	103800 KB	Output is correct
26	Correct	81 ms	104028 KB	Output is correct
27	Correct	213 ms	126012 KB	Output is correct
28	Correct	222 ms	125940 KB	Output is correct
29	Correct	430 ms	124876 KB	Output is correct
30	Correct	391 ms	124524 KB	Output is correct
31	Correct	370 ms	124600 KB	Output is correct
32	Correct	363 ms	124596 KB	Output is correct
33	Correct	409 ms	126812 KB	Output is correct
34	Correct	412 ms	126968 KB	Output is correct
35	Correct	365 ms	125416 KB	Output is correct
36	Correct	387 ms	126072 KB	Output is correct
37	Correct	416 ms	126840 KB	Output is correct
38	Correct	427 ms	129400 KB	Output is correct
39	Correct	390 ms	127608 KB	Output is correct
40	Correct	388 ms	129272 KB	Output is correct
41	Correct	411 ms	129272 KB	Output is correct
42	Correct	396 ms	128760 KB	Output is correct
43	Correct	413 ms	132004 KB	Output is correct
44	Correct	431 ms	131876 KB	Output is correct
45	Correct	380 ms	134392 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	103800 KB	Output is correct
2	Correct	92 ms	103928 KB	Output is correct
3	Correct	98 ms	103772 KB	Output is correct
4	Correct	90 ms	103796 KB	Output is correct
5	Correct	85 ms	103800 KB	Output is correct
6	Correct	88 ms	103788 KB	Output is correct
7	Correct	92 ms	103928 KB	Output is correct
8	Correct	91 ms	103800 KB	Output is correct
9	Correct	91 ms	103816 KB	Output is correct
10	Correct	90 ms	103804 KB	Output is correct
11	Correct	91 ms	103804 KB	Output is correct
12	Correct	94 ms	103984 KB	Output is correct
13	Correct	91 ms	103920 KB	Output is correct
14	Correct	82 ms	103884 KB	Output is correct
15	Correct	80 ms	103800 KB	Output is correct
16	Correct	80 ms	103800 KB	Output is correct
17	Correct	91 ms	103800 KB	Output is correct
18	Correct	95 ms	103800 KB	Output is correct
19	Correct	125 ms	103800 KB	Output is correct
20	Correct	79 ms	103928 KB	Output is correct
21	Correct	79 ms	103800 KB	Output is correct
22	Correct	80 ms	103800 KB	Output is correct
23	Correct	86 ms	103864 KB	Output is correct
24	Correct	93 ms	103800 KB	Output is correct
25	Correct	79 ms	103800 KB	Output is correct
26	Correct	81 ms	104028 KB	Output is correct
27	Correct	213 ms	126012 KB	Output is correct
28	Correct	222 ms	125940 KB	Output is correct
29	Correct	430 ms	124876 KB	Output is correct
30	Correct	391 ms	124524 KB	Output is correct
31	Correct	370 ms	124600 KB	Output is correct
32	Correct	363 ms	124596 KB	Output is correct
33	Correct	409 ms	126812 KB	Output is correct
34	Correct	412 ms	126968 KB	Output is correct
35	Correct	365 ms	125416 KB	Output is correct
36	Correct	387 ms	126072 KB	Output is correct
37	Correct	416 ms	126840 KB	Output is correct
38	Correct	427 ms	129400 KB	Output is correct
39	Correct	390 ms	127608 KB	Output is correct
40	Correct	388 ms	129272 KB	Output is correct
41	Correct	411 ms	129272 KB	Output is correct
42	Correct	396 ms	128760 KB	Output is correct
43	Correct	413 ms	132004 KB	Output is correct
44	Correct	431 ms	131876 KB	Output is correct
45	Correct	380 ms	134392 KB	Output is correct
46	Correct	359 ms	126504 KB	Output is correct
47	Correct	4224 ms	431344 KB	Output is correct
48	Correct	4599 ms	439920 KB	Output is correct
49	Correct	5112 ms	458176 KB	Output is correct
50	Correct	4802 ms	446384 KB	Output is correct
51	Correct	5023 ms	444304 KB	Output is correct
52	Correct	5568 ms	472356 KB	Output is correct
53	Correct	5758 ms	475236 KB	Output is correct
54	Correct	5580 ms	470792 KB	Output is correct
55	Correct	5608 ms	473068 KB	Output is correct
56	Correct	5622 ms	476316 KB	Output is correct
57	Correct	5369 ms	476024 KB	Output is correct
58	Correct	5752 ms	478372 KB	Output is correct
59	Correct	5540 ms	483772 KB	Output is correct
60	Correct	5625 ms	480148 KB	Output is correct
61	Correct	6059 ms	477776 KB	Output is correct
62	Correct	6129 ms	470012 KB	Output is correct
63	Correct	6083 ms	461992 KB	Output is correct
64	Correct	4186 ms	539692 KB	Output is correct
65	Correct	4206 ms	539856 KB	Output is correct

Subtask #4
38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	103800 KB	Output is correct
2	Correct	92 ms	103928 KB	Output is correct
3	Correct	98 ms	103772 KB	Output is correct
4	Correct	90 ms	103796 KB	Output is correct
5	Correct	85 ms	103800 KB	Output is correct
6	Correct	88 ms	103788 KB	Output is correct
7	Correct	92 ms	103928 KB	Output is correct
8	Correct	91 ms	103800 KB	Output is correct
9	Correct	91 ms	103816 KB	Output is correct
10	Correct	90 ms	103804 KB	Output is correct
11	Correct	91 ms	103804 KB	Output is correct
12	Correct	94 ms	103984 KB	Output is correct
13	Correct	91 ms	103920 KB	Output is correct
14	Correct	82 ms	103884 KB	Output is correct
15	Correct	80 ms	103800 KB	Output is correct
16	Correct	80 ms	103800 KB	Output is correct
17	Correct	91 ms	103800 KB	Output is correct
18	Correct	95 ms	103800 KB	Output is correct
19	Correct	125 ms	103800 KB	Output is correct
20	Correct	79 ms	103928 KB	Output is correct
21	Correct	79 ms	103800 KB	Output is correct
22	Correct	80 ms	103800 KB	Output is correct
23	Correct	86 ms	103864 KB	Output is correct
24	Correct	93 ms	103800 KB	Output is correct
25	Correct	79 ms	103800 KB	Output is correct
26	Correct	81 ms	104028 KB	Output is correct
27	Correct	213 ms	126012 KB	Output is correct
28	Correct	222 ms	125940 KB	Output is correct
29	Correct	430 ms	124876 KB	Output is correct
30	Correct	391 ms	124524 KB	Output is correct
31	Correct	370 ms	124600 KB	Output is correct
32	Correct	363 ms	124596 KB	Output is correct
33	Correct	409 ms	126812 KB	Output is correct
34	Correct	412 ms	126968 KB	Output is correct
35	Correct	365 ms	125416 KB	Output is correct
36	Correct	387 ms	126072 KB	Output is correct
37	Correct	416 ms	126840 KB	Output is correct
38	Correct	427 ms	129400 KB	Output is correct
39	Correct	390 ms	127608 KB	Output is correct
40	Correct	388 ms	129272 KB	Output is correct
41	Correct	411 ms	129272 KB	Output is correct
42	Correct	396 ms	128760 KB	Output is correct
43	Correct	413 ms	132004 KB	Output is correct
44	Correct	431 ms	131876 KB	Output is correct
45	Correct	380 ms	134392 KB	Output is correct
46	Correct	359 ms	126504 KB	Output is correct
47	Correct	4224 ms	431344 KB	Output is correct
48	Correct	4599 ms	439920 KB	Output is correct
49	Correct	5112 ms	458176 KB	Output is correct
50	Correct	4802 ms	446384 KB	Output is correct
51	Correct	5023 ms	444304 KB	Output is correct
52	Correct	5568 ms	472356 KB	Output is correct
53	Correct	5758 ms	475236 KB	Output is correct
54	Correct	5580 ms	470792 KB	Output is correct
55	Correct	5608 ms	473068 KB	Output is correct
56	Correct	5622 ms	476316 KB	Output is correct
57	Correct	5369 ms	476024 KB	Output is correct
58	Correct	5752 ms	478372 KB	Output is correct
59	Correct	5540 ms	483772 KB	Output is correct
60	Correct	5625 ms	480148 KB	Output is correct
61	Correct	6059 ms	477776 KB	Output is correct
62	Correct	6129 ms	470012 KB	Output is correct
63	Correct	6083 ms	461992 KB	Output is correct
64	Correct	4186 ms	539692 KB	Output is correct
65	Correct	4206 ms	539856 KB	Output is correct
66	Correct	305 ms	124792 KB	Output is correct
67	Correct	1584 ms	206880 KB	Output is correct
68	Correct	4501 ms	513892 KB	Output is correct
69	Correct	4879 ms	519032 KB	Output is correct
70	Correct	5455 ms	535928 KB	Output is correct
71	Correct	7268 ms	427512 KB	Output is correct
72	Correct	7428 ms	438784 KB	Output is correct
73	Correct	8425 ms	473584 KB	Output is correct
74	Correct	8714 ms	476176 KB	Output is correct
75	Correct	8507 ms	474328 KB	Output is correct
76	Correct	8143 ms	454984 KB	Output is correct
77	Correct	7878 ms	445864 KB	Output is correct
78	Correct	7736 ms	443156 KB	Output is correct
79	Correct	8358 ms	481116 KB	Output is correct
80	Correct	8479 ms	482368 KB	Output is correct
81	Correct	8052 ms	469396 KB	Output is correct
82	Correct	9040 ms	485332 KB	Output is correct
83	Correct	8816 ms	479824 KB	Output is correct
84	Correct	8923 ms	465820 KB	Output is correct
85	Correct	6380 ms	540664 KB	Output is correct

답안 #96216

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 35.0 / 35.0

Subtask #3 15.0 / 15.0

Subtask #4 38.0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
35.0 / 35.0

Subtask #3
15.0 / 15.0

Subtask #4
38.0 / 38.0