답안 #96184 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96184	2019-02-06T19:00:36 Z	jangwonyoung	Wild Boar (JOI18_wild_boar)	C++14	12 / 100	465 ms	134776 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)1e16};
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	82 ms	103800 KB	Output is correct
2	Correct	80 ms	103920 KB	Output is correct
3	Correct	82 ms	103800 KB	Output is correct
4	Correct	83 ms	103928 KB	Output is correct
5	Correct	81 ms	103800 KB	Output is correct
6	Correct	78 ms	103800 KB	Output is correct
7	Correct	82 ms	103928 KB	Output is correct
8	Correct	82 ms	103800 KB	Output is correct
9	Correct	82 ms	103772 KB	Output is correct
10	Correct	80 ms	103792 KB	Output is correct
11	Correct	82 ms	103800 KB	Output is correct
12	Correct	82 ms	103800 KB	Output is correct
13	Correct	83 ms	103800 KB	Output is correct
14	Correct	79 ms	103800 KB	Output is correct
15	Correct	79 ms	103800 KB	Output is correct
16	Correct	111 ms	103900 KB	Output is correct
17	Correct	93 ms	103800 KB	Output is correct
18	Correct	91 ms	103800 KB	Output is correct
19	Correct	86 ms	103928 KB	Output is correct
20	Correct	80 ms	103932 KB	Output is correct
21	Correct	81 ms	103800 KB	Output is correct
22	Correct	79 ms	103800 KB	Output is correct
23	Correct	81 ms	103880 KB	Output is correct
24	Correct	80 ms	103928 KB	Output is correct
25	Correct	80 ms	103928 KB	Output is correct

Subtask #2
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	82 ms	103800 KB	Output is correct
2	Correct	80 ms	103920 KB	Output is correct
3	Correct	82 ms	103800 KB	Output is correct
4	Correct	83 ms	103928 KB	Output is correct
5	Correct	81 ms	103800 KB	Output is correct
6	Correct	78 ms	103800 KB	Output is correct
7	Correct	82 ms	103928 KB	Output is correct
8	Correct	82 ms	103800 KB	Output is correct
9	Correct	82 ms	103772 KB	Output is correct
10	Correct	80 ms	103792 KB	Output is correct
11	Correct	82 ms	103800 KB	Output is correct
12	Correct	82 ms	103800 KB	Output is correct
13	Correct	83 ms	103800 KB	Output is correct
14	Correct	79 ms	103800 KB	Output is correct
15	Correct	79 ms	103800 KB	Output is correct
16	Correct	111 ms	103900 KB	Output is correct
17	Correct	93 ms	103800 KB	Output is correct
18	Correct	91 ms	103800 KB	Output is correct
19	Correct	86 ms	103928 KB	Output is correct
20	Correct	80 ms	103932 KB	Output is correct
21	Correct	81 ms	103800 KB	Output is correct
22	Correct	79 ms	103800 KB	Output is correct
23	Correct	81 ms	103880 KB	Output is correct
24	Correct	80 ms	103928 KB	Output is correct
25	Correct	80 ms	103928 KB	Output is correct
26	Correct	83 ms	103968 KB	Output is correct
27	Correct	234 ms	126088 KB	Output is correct
28	Correct	233 ms	126072 KB	Output is correct
29	Correct	378 ms	125236 KB	Output is correct
30	Correct	359 ms	124664 KB	Output is correct
31	Correct	345 ms	124900 KB	Output is correct
32	Correct	356 ms	124636 KB	Output is correct
33	Correct	381 ms	127224 KB	Output is correct
34	Correct	374 ms	127224 KB	Output is correct
35	Correct	350 ms	125928 KB	Output is correct
36	Correct	368 ms	126072 KB	Output is correct
37	Correct	380 ms	127144 KB	Output is correct
38	Correct	381 ms	129656 KB	Output is correct
39	Correct	384 ms	127992 KB	Output is correct
40	Correct	385 ms	129528 KB	Output is correct
41	Correct	392 ms	129524 KB	Output is correct
42	Correct	374 ms	128888 KB	Output is correct
43	Correct	390 ms	132216 KB	Output is correct
44	Correct	465 ms	132344 KB	Output is correct
45	Incorrect	354 ms	134776 KB	Output isn't correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	82 ms	103800 KB	Output is correct
2	Correct	80 ms	103920 KB	Output is correct
3	Correct	82 ms	103800 KB	Output is correct
4	Correct	83 ms	103928 KB	Output is correct
5	Correct	81 ms	103800 KB	Output is correct
6	Correct	78 ms	103800 KB	Output is correct
7	Correct	82 ms	103928 KB	Output is correct
8	Correct	82 ms	103800 KB	Output is correct
9	Correct	82 ms	103772 KB	Output is correct
10	Correct	80 ms	103792 KB	Output is correct
11	Correct	82 ms	103800 KB	Output is correct
12	Correct	82 ms	103800 KB	Output is correct
13	Correct	83 ms	103800 KB	Output is correct
14	Correct	79 ms	103800 KB	Output is correct
15	Correct	79 ms	103800 KB	Output is correct
16	Correct	111 ms	103900 KB	Output is correct
17	Correct	93 ms	103800 KB	Output is correct
18	Correct	91 ms	103800 KB	Output is correct
19	Correct	86 ms	103928 KB	Output is correct
20	Correct	80 ms	103932 KB	Output is correct
21	Correct	81 ms	103800 KB	Output is correct
22	Correct	79 ms	103800 KB	Output is correct
23	Correct	81 ms	103880 KB	Output is correct
24	Correct	80 ms	103928 KB	Output is correct
25	Correct	80 ms	103928 KB	Output is correct
26	Correct	83 ms	103968 KB	Output is correct
27	Correct	234 ms	126088 KB	Output is correct
28	Correct	233 ms	126072 KB	Output is correct
29	Correct	378 ms	125236 KB	Output is correct
30	Correct	359 ms	124664 KB	Output is correct
31	Correct	345 ms	124900 KB	Output is correct
32	Correct	356 ms	124636 KB	Output is correct
33	Correct	381 ms	127224 KB	Output is correct
34	Correct	374 ms	127224 KB	Output is correct
35	Correct	350 ms	125928 KB	Output is correct
36	Correct	368 ms	126072 KB	Output is correct
37	Correct	380 ms	127144 KB	Output is correct
38	Correct	381 ms	129656 KB	Output is correct
39	Correct	384 ms	127992 KB	Output is correct
40	Correct	385 ms	129528 KB	Output is correct
41	Correct	392 ms	129524 KB	Output is correct
42	Correct	374 ms	128888 KB	Output is correct
43	Correct	390 ms	132216 KB	Output is correct
44	Correct	465 ms	132344 KB	Output is correct
45	Incorrect	354 ms	134776 KB	Output isn't correct

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	82 ms	103800 KB	Output is correct
2	Correct	80 ms	103920 KB	Output is correct
3	Correct	82 ms	103800 KB	Output is correct
4	Correct	83 ms	103928 KB	Output is correct
5	Correct	81 ms	103800 KB	Output is correct
6	Correct	78 ms	103800 KB	Output is correct
7	Correct	82 ms	103928 KB	Output is correct
8	Correct	82 ms	103800 KB	Output is correct
9	Correct	82 ms	103772 KB	Output is correct
10	Correct	80 ms	103792 KB	Output is correct
11	Correct	82 ms	103800 KB	Output is correct
12	Correct	82 ms	103800 KB	Output is correct
13	Correct	83 ms	103800 KB	Output is correct
14	Correct	79 ms	103800 KB	Output is correct
15	Correct	79 ms	103800 KB	Output is correct
16	Correct	111 ms	103900 KB	Output is correct
17	Correct	93 ms	103800 KB	Output is correct
18	Correct	91 ms	103800 KB	Output is correct
19	Correct	86 ms	103928 KB	Output is correct
20	Correct	80 ms	103932 KB	Output is correct
21	Correct	81 ms	103800 KB	Output is correct
22	Correct	79 ms	103800 KB	Output is correct
23	Correct	81 ms	103880 KB	Output is correct
24	Correct	80 ms	103928 KB	Output is correct
25	Correct	80 ms	103928 KB	Output is correct
26	Correct	83 ms	103968 KB	Output is correct
27	Correct	234 ms	126088 KB	Output is correct
28	Correct	233 ms	126072 KB	Output is correct
29	Correct	378 ms	125236 KB	Output is correct
30	Correct	359 ms	124664 KB	Output is correct
31	Correct	345 ms	124900 KB	Output is correct
32	Correct	356 ms	124636 KB	Output is correct
33	Correct	381 ms	127224 KB	Output is correct
34	Correct	374 ms	127224 KB	Output is correct
35	Correct	350 ms	125928 KB	Output is correct
36	Correct	368 ms	126072 KB	Output is correct
37	Correct	380 ms	127144 KB	Output is correct
38	Correct	381 ms	129656 KB	Output is correct
39	Correct	384 ms	127992 KB	Output is correct
40	Correct	385 ms	129528 KB	Output is correct
41	Correct	392 ms	129524 KB	Output is correct
42	Correct	374 ms	128888 KB	Output is correct
43	Correct	390 ms	132216 KB	Output is correct
44	Correct	465 ms	132344 KB	Output is correct
45	Incorrect	354 ms	134776 KB	Output isn't correct

답안 #96184

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