답안 #96188 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96188	2019-02-06T19:20:40 Z	jangwonyoung	Wild Boar (JOI18_wild_boar)	C++14	12 / 100	514 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)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	82 ms	103800 KB	Output is correct
2	Correct	85 ms	103800 KB	Output is correct
3	Correct	79 ms	103800 KB	Output is correct
4	Correct	79 ms	103800 KB	Output is correct
5	Correct	81 ms	103852 KB	Output is correct
6	Correct	80 ms	103800 KB	Output is correct
7	Correct	81 ms	103800 KB	Output is correct
8	Correct	79 ms	103672 KB	Output is correct
9	Correct	78 ms	103800 KB	Output is correct
10	Correct	82 ms	103800 KB	Output is correct
11	Correct	79 ms	103800 KB	Output is correct
12	Correct	80 ms	103888 KB	Output is correct
13	Correct	81 ms	103800 KB	Output is correct
14	Correct	82 ms	103800 KB	Output is correct
15	Correct	81 ms	103800 KB	Output is correct
16	Correct	79 ms	103800 KB	Output is correct
17	Correct	78 ms	103928 KB	Output is correct
18	Correct	79 ms	103800 KB	Output is correct
19	Correct	79 ms	103800 KB	Output is correct
20	Correct	85 ms	103800 KB	Output is correct
21	Correct	79 ms	103900 KB	Output is correct
22	Correct	83 ms	103860 KB	Output is correct
23	Correct	78 ms	103800 KB	Output is correct
24	Correct	79 ms	103800 KB	Output is correct
25	Correct	79 ms	103800 KB	Output is correct

Subtask #2
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	82 ms	103800 KB	Output is correct
2	Correct	85 ms	103800 KB	Output is correct
3	Correct	79 ms	103800 KB	Output is correct
4	Correct	79 ms	103800 KB	Output is correct
5	Correct	81 ms	103852 KB	Output is correct
6	Correct	80 ms	103800 KB	Output is correct
7	Correct	81 ms	103800 KB	Output is correct
8	Correct	79 ms	103672 KB	Output is correct
9	Correct	78 ms	103800 KB	Output is correct
10	Correct	82 ms	103800 KB	Output is correct
11	Correct	79 ms	103800 KB	Output is correct
12	Correct	80 ms	103888 KB	Output is correct
13	Correct	81 ms	103800 KB	Output is correct
14	Correct	82 ms	103800 KB	Output is correct
15	Correct	81 ms	103800 KB	Output is correct
16	Correct	79 ms	103800 KB	Output is correct
17	Correct	78 ms	103928 KB	Output is correct
18	Correct	79 ms	103800 KB	Output is correct
19	Correct	79 ms	103800 KB	Output is correct
20	Correct	85 ms	103800 KB	Output is correct
21	Correct	79 ms	103900 KB	Output is correct
22	Correct	83 ms	103860 KB	Output is correct
23	Correct	78 ms	103800 KB	Output is correct
24	Correct	79 ms	103800 KB	Output is correct
25	Correct	79 ms	103800 KB	Output is correct
26	Correct	83 ms	104056 KB	Output is correct
27	Correct	204 ms	126352 KB	Output is correct
28	Correct	191 ms	126388 KB	Output is correct
29	Correct	410 ms	125236 KB	Output is correct
30	Correct	377 ms	124676 KB	Output is correct
31	Correct	348 ms	124772 KB	Output is correct
32	Correct	354 ms	124632 KB	Output is correct
33	Correct	420 ms	127352 KB	Output is correct
34	Correct	407 ms	127224 KB	Output is correct
35	Correct	344 ms	125800 KB	Output is correct
36	Correct	381 ms	126268 KB	Output is correct
37	Correct	514 ms	127352 KB	Output is correct
38	Correct	388 ms	129784 KB	Output is correct
39	Correct	369 ms	127992 KB	Output is correct
40	Correct	388 ms	129656 KB	Output is correct
41	Correct	392 ms	129656 KB	Output is correct
42	Correct	372 ms	128888 KB	Output is correct
43	Correct	389 ms	132216 KB	Output is correct
44	Correct	391 ms	132456 KB	Output is correct
45	Incorrect	331 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	85 ms	103800 KB	Output is correct
3	Correct	79 ms	103800 KB	Output is correct
4	Correct	79 ms	103800 KB	Output is correct
5	Correct	81 ms	103852 KB	Output is correct
6	Correct	80 ms	103800 KB	Output is correct
7	Correct	81 ms	103800 KB	Output is correct
8	Correct	79 ms	103672 KB	Output is correct
9	Correct	78 ms	103800 KB	Output is correct
10	Correct	82 ms	103800 KB	Output is correct
11	Correct	79 ms	103800 KB	Output is correct
12	Correct	80 ms	103888 KB	Output is correct
13	Correct	81 ms	103800 KB	Output is correct
14	Correct	82 ms	103800 KB	Output is correct
15	Correct	81 ms	103800 KB	Output is correct
16	Correct	79 ms	103800 KB	Output is correct
17	Correct	78 ms	103928 KB	Output is correct
18	Correct	79 ms	103800 KB	Output is correct
19	Correct	79 ms	103800 KB	Output is correct
20	Correct	85 ms	103800 KB	Output is correct
21	Correct	79 ms	103900 KB	Output is correct
22	Correct	83 ms	103860 KB	Output is correct
23	Correct	78 ms	103800 KB	Output is correct
24	Correct	79 ms	103800 KB	Output is correct
25	Correct	79 ms	103800 KB	Output is correct
26	Correct	83 ms	104056 KB	Output is correct
27	Correct	204 ms	126352 KB	Output is correct
28	Correct	191 ms	126388 KB	Output is correct
29	Correct	410 ms	125236 KB	Output is correct
30	Correct	377 ms	124676 KB	Output is correct
31	Correct	348 ms	124772 KB	Output is correct
32	Correct	354 ms	124632 KB	Output is correct
33	Correct	420 ms	127352 KB	Output is correct
34	Correct	407 ms	127224 KB	Output is correct
35	Correct	344 ms	125800 KB	Output is correct
36	Correct	381 ms	126268 KB	Output is correct
37	Correct	514 ms	127352 KB	Output is correct
38	Correct	388 ms	129784 KB	Output is correct
39	Correct	369 ms	127992 KB	Output is correct
40	Correct	388 ms	129656 KB	Output is correct
41	Correct	392 ms	129656 KB	Output is correct
42	Correct	372 ms	128888 KB	Output is correct
43	Correct	389 ms	132216 KB	Output is correct
44	Correct	391 ms	132456 KB	Output is correct
45	Incorrect	331 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	85 ms	103800 KB	Output is correct
3	Correct	79 ms	103800 KB	Output is correct
4	Correct	79 ms	103800 KB	Output is correct
5	Correct	81 ms	103852 KB	Output is correct
6	Correct	80 ms	103800 KB	Output is correct
7	Correct	81 ms	103800 KB	Output is correct
8	Correct	79 ms	103672 KB	Output is correct
9	Correct	78 ms	103800 KB	Output is correct
10	Correct	82 ms	103800 KB	Output is correct
11	Correct	79 ms	103800 KB	Output is correct
12	Correct	80 ms	103888 KB	Output is correct
13	Correct	81 ms	103800 KB	Output is correct
14	Correct	82 ms	103800 KB	Output is correct
15	Correct	81 ms	103800 KB	Output is correct
16	Correct	79 ms	103800 KB	Output is correct
17	Correct	78 ms	103928 KB	Output is correct
18	Correct	79 ms	103800 KB	Output is correct
19	Correct	79 ms	103800 KB	Output is correct
20	Correct	85 ms	103800 KB	Output is correct
21	Correct	79 ms	103900 KB	Output is correct
22	Correct	83 ms	103860 KB	Output is correct
23	Correct	78 ms	103800 KB	Output is correct
24	Correct	79 ms	103800 KB	Output is correct
25	Correct	79 ms	103800 KB	Output is correct
26	Correct	83 ms	104056 KB	Output is correct
27	Correct	204 ms	126352 KB	Output is correct
28	Correct	191 ms	126388 KB	Output is correct
29	Correct	410 ms	125236 KB	Output is correct
30	Correct	377 ms	124676 KB	Output is correct
31	Correct	348 ms	124772 KB	Output is correct
32	Correct	354 ms	124632 KB	Output is correct
33	Correct	420 ms	127352 KB	Output is correct
34	Correct	407 ms	127224 KB	Output is correct
35	Correct	344 ms	125800 KB	Output is correct
36	Correct	381 ms	126268 KB	Output is correct
37	Correct	514 ms	127352 KB	Output is correct
38	Correct	388 ms	129784 KB	Output is correct
39	Correct	369 ms	127992 KB	Output is correct
40	Correct	388 ms	129656 KB	Output is correct
41	Correct	392 ms	129656 KB	Output is correct
42	Correct	372 ms	128888 KB	Output is correct
43	Correct	389 ms	132216 KB	Output is correct
44	Correct	391 ms	132456 KB	Output is correct
45	Incorrect	331 ms	134776 KB	Output isn't correct

답안 #96188

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