답안 #96215 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96215	2019-02-07T06:17:04 Z	jangwonyoung	Wild Boar (JOI18_wild_boar)	C++14	12 / 100	427 ms	134904 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)1e15};
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]=1e15;
			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>=1e15) cout << "-1\n";
		else cout << ans << '\n';
	}
	
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	83 ms	103800 KB	Output is correct
2	Correct	79 ms	103860 KB	Output is correct
3	Correct	99 ms	103800 KB	Output is correct
4	Correct	93 ms	103800 KB	Output is correct
5	Correct	102 ms	103800 KB	Output is correct
6	Correct	89 ms	103800 KB	Output is correct
7	Correct	78 ms	103760 KB	Output is correct
8	Correct	91 ms	103800 KB	Output is correct
9	Correct	80 ms	103800 KB	Output is correct
10	Correct	93 ms	103916 KB	Output is correct
11	Correct	81 ms	103800 KB	Output is correct
12	Correct	94 ms	103844 KB	Output is correct
13	Correct	95 ms	103800 KB	Output is correct
14	Correct	92 ms	103928 KB	Output is correct
15	Correct	113 ms	103800 KB	Output is correct
16	Correct	92 ms	103804 KB	Output is correct
17	Correct	92 ms	103928 KB	Output is correct
18	Correct	92 ms	103800 KB	Output is correct
19	Correct	93 ms	103800 KB	Output is correct
20	Correct	90 ms	103800 KB	Output is correct
21	Correct	91 ms	103772 KB	Output is correct
22	Correct	90 ms	103800 KB	Output is correct
23	Correct	89 ms	103880 KB	Output is correct
24	Correct	92 ms	103896 KB	Output is correct
25	Correct	79 ms	103772 KB	Output is correct

Subtask #2
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	83 ms	103800 KB	Output is correct
2	Correct	79 ms	103860 KB	Output is correct
3	Correct	99 ms	103800 KB	Output is correct
4	Correct	93 ms	103800 KB	Output is correct
5	Correct	102 ms	103800 KB	Output is correct
6	Correct	89 ms	103800 KB	Output is correct
7	Correct	78 ms	103760 KB	Output is correct
8	Correct	91 ms	103800 KB	Output is correct
9	Correct	80 ms	103800 KB	Output is correct
10	Correct	93 ms	103916 KB	Output is correct
11	Correct	81 ms	103800 KB	Output is correct
12	Correct	94 ms	103844 KB	Output is correct
13	Correct	95 ms	103800 KB	Output is correct
14	Correct	92 ms	103928 KB	Output is correct
15	Correct	113 ms	103800 KB	Output is correct
16	Correct	92 ms	103804 KB	Output is correct
17	Correct	92 ms	103928 KB	Output is correct
18	Correct	92 ms	103800 KB	Output is correct
19	Correct	93 ms	103800 KB	Output is correct
20	Correct	90 ms	103800 KB	Output is correct
21	Correct	91 ms	103772 KB	Output is correct
22	Correct	90 ms	103800 KB	Output is correct
23	Correct	89 ms	103880 KB	Output is correct
24	Correct	92 ms	103896 KB	Output is correct
25	Correct	79 ms	103772 KB	Output is correct
26	Correct	102 ms	104028 KB	Output is correct
27	Correct	231 ms	126328 KB	Output is correct
28	Correct	198 ms	126200 KB	Output is correct
29	Correct	403 ms	125136 KB	Output is correct
30	Correct	359 ms	124652 KB	Output is correct
31	Correct	367 ms	124696 KB	Output is correct
32	Correct	359 ms	124628 KB	Output is correct
33	Correct	393 ms	127348 KB	Output is correct
34	Correct	388 ms	127224 KB	Output is correct
35	Correct	332 ms	125672 KB	Output is correct
36	Correct	372 ms	126044 KB	Output is correct
37	Correct	387 ms	127224 KB	Output is correct
38	Correct	396 ms	129692 KB	Output is correct
39	Correct	371 ms	127940 KB	Output is correct
40	Correct	389 ms	129572 KB	Output is correct
41	Correct	424 ms	129680 KB	Output is correct
42	Correct	383 ms	128812 KB	Output is correct
43	Correct	407 ms	132360 KB	Output is correct
44	Correct	427 ms	132252 KB	Output is correct
45	Incorrect	329 ms	134904 KB	Output isn't correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	83 ms	103800 KB	Output is correct
2	Correct	79 ms	103860 KB	Output is correct
3	Correct	99 ms	103800 KB	Output is correct
4	Correct	93 ms	103800 KB	Output is correct
5	Correct	102 ms	103800 KB	Output is correct
6	Correct	89 ms	103800 KB	Output is correct
7	Correct	78 ms	103760 KB	Output is correct
8	Correct	91 ms	103800 KB	Output is correct
9	Correct	80 ms	103800 KB	Output is correct
10	Correct	93 ms	103916 KB	Output is correct
11	Correct	81 ms	103800 KB	Output is correct
12	Correct	94 ms	103844 KB	Output is correct
13	Correct	95 ms	103800 KB	Output is correct
14	Correct	92 ms	103928 KB	Output is correct
15	Correct	113 ms	103800 KB	Output is correct
16	Correct	92 ms	103804 KB	Output is correct
17	Correct	92 ms	103928 KB	Output is correct
18	Correct	92 ms	103800 KB	Output is correct
19	Correct	93 ms	103800 KB	Output is correct
20	Correct	90 ms	103800 KB	Output is correct
21	Correct	91 ms	103772 KB	Output is correct
22	Correct	90 ms	103800 KB	Output is correct
23	Correct	89 ms	103880 KB	Output is correct
24	Correct	92 ms	103896 KB	Output is correct
25	Correct	79 ms	103772 KB	Output is correct
26	Correct	102 ms	104028 KB	Output is correct
27	Correct	231 ms	126328 KB	Output is correct
28	Correct	198 ms	126200 KB	Output is correct
29	Correct	403 ms	125136 KB	Output is correct
30	Correct	359 ms	124652 KB	Output is correct
31	Correct	367 ms	124696 KB	Output is correct
32	Correct	359 ms	124628 KB	Output is correct
33	Correct	393 ms	127348 KB	Output is correct
34	Correct	388 ms	127224 KB	Output is correct
35	Correct	332 ms	125672 KB	Output is correct
36	Correct	372 ms	126044 KB	Output is correct
37	Correct	387 ms	127224 KB	Output is correct
38	Correct	396 ms	129692 KB	Output is correct
39	Correct	371 ms	127940 KB	Output is correct
40	Correct	389 ms	129572 KB	Output is correct
41	Correct	424 ms	129680 KB	Output is correct
42	Correct	383 ms	128812 KB	Output is correct
43	Correct	407 ms	132360 KB	Output is correct
44	Correct	427 ms	132252 KB	Output is correct
45	Incorrect	329 ms	134904 KB	Output isn't correct

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	83 ms	103800 KB	Output is correct
2	Correct	79 ms	103860 KB	Output is correct
3	Correct	99 ms	103800 KB	Output is correct
4	Correct	93 ms	103800 KB	Output is correct
5	Correct	102 ms	103800 KB	Output is correct
6	Correct	89 ms	103800 KB	Output is correct
7	Correct	78 ms	103760 KB	Output is correct
8	Correct	91 ms	103800 KB	Output is correct
9	Correct	80 ms	103800 KB	Output is correct
10	Correct	93 ms	103916 KB	Output is correct
11	Correct	81 ms	103800 KB	Output is correct
12	Correct	94 ms	103844 KB	Output is correct
13	Correct	95 ms	103800 KB	Output is correct
14	Correct	92 ms	103928 KB	Output is correct
15	Correct	113 ms	103800 KB	Output is correct
16	Correct	92 ms	103804 KB	Output is correct
17	Correct	92 ms	103928 KB	Output is correct
18	Correct	92 ms	103800 KB	Output is correct
19	Correct	93 ms	103800 KB	Output is correct
20	Correct	90 ms	103800 KB	Output is correct
21	Correct	91 ms	103772 KB	Output is correct
22	Correct	90 ms	103800 KB	Output is correct
23	Correct	89 ms	103880 KB	Output is correct
24	Correct	92 ms	103896 KB	Output is correct
25	Correct	79 ms	103772 KB	Output is correct
26	Correct	102 ms	104028 KB	Output is correct
27	Correct	231 ms	126328 KB	Output is correct
28	Correct	198 ms	126200 KB	Output is correct
29	Correct	403 ms	125136 KB	Output is correct
30	Correct	359 ms	124652 KB	Output is correct
31	Correct	367 ms	124696 KB	Output is correct
32	Correct	359 ms	124628 KB	Output is correct
33	Correct	393 ms	127348 KB	Output is correct
34	Correct	388 ms	127224 KB	Output is correct
35	Correct	332 ms	125672 KB	Output is correct
36	Correct	372 ms	126044 KB	Output is correct
37	Correct	387 ms	127224 KB	Output is correct
38	Correct	396 ms	129692 KB	Output is correct
39	Correct	371 ms	127940 KB	Output is correct
40	Correct	389 ms	129572 KB	Output is correct
41	Correct	424 ms	129680 KB	Output is correct
42	Correct	383 ms	128812 KB	Output is correct
43	Correct	407 ms	132360 KB	Output is correct
44	Correct	427 ms	132252 KB	Output is correct
45	Incorrect	329 ms	134904 KB	Output isn't correct

답안 #96215

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 35.0

Subtask #3 0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 35.0

Subtask #3
0 / 15.0

Subtask #4
0 / 38.0