Submission #563858

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
563858	2022-05-18T07:33:54 Z	errorgorn	Wild Boar (JOI18_wild_boar)	C++17	62 / 100	18000 ms	457924 KB

wild_boar

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define i3 tuple<int,int,int>
#define i4 tuple<int,int,int,int>
#define fi first
#define se second
//#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,m,l,q;
struct E{ int to,w,id; };
vector<E> al[2005];

vector<ii> w[2005]; //ok so we store the best 2 guys...
priority_queue<i4,vector<i4>,greater<i4> > pq;

void add(int i,ii val){
	if (w[i][0]==val || w[i][1]==val) return; //prevent from inserting dupes
	
	//cout<<i<<" "<<val.fi<<" "<<val.se<<endl;
	//rep(x,0,2) cout<<w[i][x].fi<<" "<<w[i][x].se<<endl;
	
	if (val.fi<w[i][0].fi){
		if (val.fi!=w[i][0].fi){
			swap(w[i][0],w[i][1]);
			pq.push({w[i][1].fi,w[i][1].se,i,1});
		}
		w[i][0]=val;
		pq.push({w[i][0].fi,w[i][0].se,i,0});
	}
	else if (val.fi<w[i][1].fi && w[i][0].se!=val.se){
		w[i][1]=val;
		pq.push({w[i][1].fi,w[i][1].se,i,1});
	}
	
	assert(w[i][0].se!=w[i][1].se);
}

struct dat{
	vector<i3> res;
	dat(){};
	dat (vector<i3> temp){ //pick best X
		map<int,int> m1,m2;
		set<ii> s;
		sort(all(temp));
		
		for (auto [w,a,b]:temp){
			if (m1[a]==2 || m2[b]==2 || s.count({a,b})) continue;
			m1[a]++,m2[b]++;
			s.insert({a,b});
			res.pub({w,a,b});
			if (sz(res)==5) break;
		}
	}
};

dat merge(dat i,dat j){
	vector<i3> temp;
	for (auto [w,id1,id2]:i.res) for (auto [w2,id3,id4]:j.res){
		if (id2!=id3) temp.pub({w+w2,id1,id4}); 
	}
	return dat(temp);
}

vector<i3> v[2005];
dat trans[2005][2005];
int arr[100005];

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>m>>q>>l;
	
	int a,b,c;
	rep(x,0,m){
		cin>>a>>b>>c;
		al[a].pub({b,c,x});
		al[b].pub({a,c,x});
	}
	
	rep(x,1,n+1){
		rep(y,1,n+1) v[y].clear();
		
		for (auto [y,_W,id]:al[x]){
			rep(x,1,n+1){
				w[x].clear();
				rep(y,1,3) w[x].pub({1e18,-y});
			}
			add(y,{_W,id});
			
			while (!pq.empty()){
				int W,id,u,pos;
				tie(W,id,u,pos)=pq.top(),pq.pop();
				if (w[u][pos]!=ii(W,id)) continue;
				
				for (auto [it,w2,id2]:al[u]) if (id!=id2){
					add(it,{W+w2,id2});
				}
			}
			
			rep(y,1,n+1) for (auto [w,id2]:w[y]) if (w<1e18){
				v[y].pub({w,id,id2});
			}
		}
		
		rep(y,1,n+1) trans[x][y]=dat(v[y]);
	}
	
	rep(x,1,l+1) cin>>arr[x];
	
	while (q--){
		cin>>a>>b;
		arr[a]=b;
		
		//rep(x,1,l+1) cout<<arr[x]<<" "; cout<<endl;
		dat ans=trans[arr[1]][arr[2]];
		rep(x,2,l){
			ans=merge(ans,trans[arr[x]][arr[x+1]]);
			//cout<<x<<":"<<endl;
			//for (auto [w,id,id2]:ans.res) cout<<w<<" "<<id<<" "<<id2<<endl;
		}
		if (ans.res.empty()) cout<<"-1"<<endl;
		else cout<<get<0>(ans.res[0])<<endl;
	}
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	94808 KB	Output is correct
2	Correct	50 ms	94764 KB	Output is correct
3	Correct	45 ms	94824 KB	Output is correct
4	Correct	45 ms	94844 KB	Output is correct
5	Correct	44 ms	94848 KB	Output is correct
6	Correct	43 ms	94804 KB	Output is correct
7	Correct	44 ms	94868 KB	Output is correct
8	Correct	44 ms	94768 KB	Output is correct
9	Correct	44 ms	94832 KB	Output is correct
10	Correct	45 ms	94788 KB	Output is correct
11	Correct	44 ms	94860 KB	Output is correct
12	Correct	44 ms	94836 KB	Output is correct
13	Correct	44 ms	94772 KB	Output is correct
14	Correct	45 ms	94764 KB	Output is correct
15	Correct	45 ms	94860 KB	Output is correct
16	Correct	44 ms	94796 KB	Output is correct
17	Correct	45 ms	94796 KB	Output is correct
18	Correct	44 ms	94788 KB	Output is correct
19	Correct	44 ms	94796 KB	Output is correct
20	Correct	45 ms	94796 KB	Output is correct
21	Correct	45 ms	94804 KB	Output is correct
22	Correct	47 ms	94936 KB	Output is correct
23	Correct	47 ms	94888 KB	Output is correct
24	Correct	45 ms	94868 KB	Output is correct
25	Correct	44 ms	94816 KB	Output is correct

Subtask #2
35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	94808 KB	Output is correct
2	Correct	50 ms	94764 KB	Output is correct
3	Correct	45 ms	94824 KB	Output is correct
4	Correct	45 ms	94844 KB	Output is correct
5	Correct	44 ms	94848 KB	Output is correct
6	Correct	43 ms	94804 KB	Output is correct
7	Correct	44 ms	94868 KB	Output is correct
8	Correct	44 ms	94768 KB	Output is correct
9	Correct	44 ms	94832 KB	Output is correct
10	Correct	45 ms	94788 KB	Output is correct
11	Correct	44 ms	94860 KB	Output is correct
12	Correct	44 ms	94836 KB	Output is correct
13	Correct	44 ms	94772 KB	Output is correct
14	Correct	45 ms	94764 KB	Output is correct
15	Correct	45 ms	94860 KB	Output is correct
16	Correct	44 ms	94796 KB	Output is correct
17	Correct	45 ms	94796 KB	Output is correct
18	Correct	44 ms	94788 KB	Output is correct
19	Correct	44 ms	94796 KB	Output is correct
20	Correct	45 ms	94796 KB	Output is correct
21	Correct	45 ms	94804 KB	Output is correct
22	Correct	47 ms	94936 KB	Output is correct
23	Correct	47 ms	94888 KB	Output is correct
24	Correct	45 ms	94868 KB	Output is correct
25	Correct	44 ms	94816 KB	Output is correct
26	Correct	45 ms	94932 KB	Output is correct
27	Correct	62 ms	96100 KB	Output is correct
28	Correct	64 ms	95976 KB	Output is correct
29	Correct	213 ms	97696 KB	Output is correct
30	Correct	213 ms	97452 KB	Output is correct
31	Correct	242 ms	97580 KB	Output is correct
32	Correct	236 ms	97688 KB	Output is correct
33	Correct	227 ms	99744 KB	Output is correct
34	Correct	230 ms	99660 KB	Output is correct
35	Correct	241 ms	99660 KB	Output is correct
36	Correct	256 ms	99260 KB	Output is correct
37	Correct	230 ms	100024 KB	Output is correct
38	Correct	245 ms	101300 KB	Output is correct
39	Correct	267 ms	101136 KB	Output is correct
40	Correct	245 ms	101400 KB	Output is correct
41	Correct	246 ms	101400 KB	Output is correct
42	Correct	270 ms	102476 KB	Output is correct
43	Correct	252 ms	103372 KB	Output is correct
44	Correct	251 ms	103372 KB	Output is correct
45	Correct	178 ms	101612 KB	Output is correct

Subtask #3
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	94808 KB	Output is correct
2	Correct	50 ms	94764 KB	Output is correct
3	Correct	45 ms	94824 KB	Output is correct
4	Correct	45 ms	94844 KB	Output is correct
5	Correct	44 ms	94848 KB	Output is correct
6	Correct	43 ms	94804 KB	Output is correct
7	Correct	44 ms	94868 KB	Output is correct
8	Correct	44 ms	94768 KB	Output is correct
9	Correct	44 ms	94832 KB	Output is correct
10	Correct	45 ms	94788 KB	Output is correct
11	Correct	44 ms	94860 KB	Output is correct
12	Correct	44 ms	94836 KB	Output is correct
13	Correct	44 ms	94772 KB	Output is correct
14	Correct	45 ms	94764 KB	Output is correct
15	Correct	45 ms	94860 KB	Output is correct
16	Correct	44 ms	94796 KB	Output is correct
17	Correct	45 ms	94796 KB	Output is correct
18	Correct	44 ms	94788 KB	Output is correct
19	Correct	44 ms	94796 KB	Output is correct
20	Correct	45 ms	94796 KB	Output is correct
21	Correct	45 ms	94804 KB	Output is correct
22	Correct	47 ms	94936 KB	Output is correct
23	Correct	47 ms	94888 KB	Output is correct
24	Correct	45 ms	94868 KB	Output is correct
25	Correct	44 ms	94816 KB	Output is correct
26	Correct	45 ms	94932 KB	Output is correct
27	Correct	62 ms	96100 KB	Output is correct
28	Correct	64 ms	95976 KB	Output is correct
29	Correct	213 ms	97696 KB	Output is correct
30	Correct	213 ms	97452 KB	Output is correct
31	Correct	242 ms	97580 KB	Output is correct
32	Correct	236 ms	97688 KB	Output is correct
33	Correct	227 ms	99744 KB	Output is correct
34	Correct	230 ms	99660 KB	Output is correct
35	Correct	241 ms	99660 KB	Output is correct
36	Correct	256 ms	99260 KB	Output is correct
37	Correct	230 ms	100024 KB	Output is correct
38	Correct	245 ms	101300 KB	Output is correct
39	Correct	267 ms	101136 KB	Output is correct
40	Correct	245 ms	101400 KB	Output is correct
41	Correct	246 ms	101400 KB	Output is correct
42	Correct	270 ms	102476 KB	Output is correct
43	Correct	252 ms	103372 KB	Output is correct
44	Correct	251 ms	103372 KB	Output is correct
45	Correct	178 ms	101612 KB	Output is correct
46	Correct	221 ms	102044 KB	Output is correct
47	Correct	2156 ms	138660 KB	Output is correct
48	Correct	2905 ms	184064 KB	Output is correct
49	Correct	3423 ms	225384 KB	Output is correct
50	Correct	3440 ms	231024 KB	Output is correct
51	Correct	3371 ms	232100 KB	Output is correct
52	Correct	3653 ms	262884 KB	Output is correct
53	Correct	3670 ms	261912 KB	Output is correct
54	Correct	3691 ms	261492 KB	Output is correct
55	Correct	3702 ms	258972 KB	Output is correct
56	Correct	4008 ms	283396 KB	Output is correct
57	Correct	4290 ms	309452 KB	Output is correct
58	Correct	4526 ms	329532 KB	Output is correct
59	Correct	4770 ms	353612 KB	Output is correct
60	Correct	5035 ms	375972 KB	Output is correct
61	Correct	5302 ms	399772 KB	Output is correct
62	Correct	5493 ms	427344 KB	Output is correct
63	Correct	5950 ms	457924 KB	Output is correct
64	Correct	4169 ms	346960 KB	Output is correct
65	Correct	4105 ms	347012 KB	Output is correct

Subtask #4
0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	94808 KB	Output is correct
2	Correct	50 ms	94764 KB	Output is correct
3	Correct	45 ms	94824 KB	Output is correct
4	Correct	45 ms	94844 KB	Output is correct
5	Correct	44 ms	94848 KB	Output is correct
6	Correct	43 ms	94804 KB	Output is correct
7	Correct	44 ms	94868 KB	Output is correct
8	Correct	44 ms	94768 KB	Output is correct
9	Correct	44 ms	94832 KB	Output is correct
10	Correct	45 ms	94788 KB	Output is correct
11	Correct	44 ms	94860 KB	Output is correct
12	Correct	44 ms	94836 KB	Output is correct
13	Correct	44 ms	94772 KB	Output is correct
14	Correct	45 ms	94764 KB	Output is correct
15	Correct	45 ms	94860 KB	Output is correct
16	Correct	44 ms	94796 KB	Output is correct
17	Correct	45 ms	94796 KB	Output is correct
18	Correct	44 ms	94788 KB	Output is correct
19	Correct	44 ms	94796 KB	Output is correct
20	Correct	45 ms	94796 KB	Output is correct
21	Correct	45 ms	94804 KB	Output is correct
22	Correct	47 ms	94936 KB	Output is correct
23	Correct	47 ms	94888 KB	Output is correct
24	Correct	45 ms	94868 KB	Output is correct
25	Correct	44 ms	94816 KB	Output is correct
26	Correct	45 ms	94932 KB	Output is correct
27	Correct	62 ms	96100 KB	Output is correct
28	Correct	64 ms	95976 KB	Output is correct
29	Correct	213 ms	97696 KB	Output is correct
30	Correct	213 ms	97452 KB	Output is correct
31	Correct	242 ms	97580 KB	Output is correct
32	Correct	236 ms	97688 KB	Output is correct
33	Correct	227 ms	99744 KB	Output is correct
34	Correct	230 ms	99660 KB	Output is correct
35	Correct	241 ms	99660 KB	Output is correct
36	Correct	256 ms	99260 KB	Output is correct
37	Correct	230 ms	100024 KB	Output is correct
38	Correct	245 ms	101300 KB	Output is correct
39	Correct	267 ms	101136 KB	Output is correct
40	Correct	245 ms	101400 KB	Output is correct
41	Correct	246 ms	101400 KB	Output is correct
42	Correct	270 ms	102476 KB	Output is correct
43	Correct	252 ms	103372 KB	Output is correct
44	Correct	251 ms	103372 KB	Output is correct
45	Correct	178 ms	101612 KB	Output is correct
46	Correct	221 ms	102044 KB	Output is correct
47	Correct	2156 ms	138660 KB	Output is correct
48	Correct	2905 ms	184064 KB	Output is correct
49	Correct	3423 ms	225384 KB	Output is correct
50	Correct	3440 ms	231024 KB	Output is correct
51	Correct	3371 ms	232100 KB	Output is correct
52	Correct	3653 ms	262884 KB	Output is correct
53	Correct	3670 ms	261912 KB	Output is correct
54	Correct	3691 ms	261492 KB	Output is correct
55	Correct	3702 ms	258972 KB	Output is correct
56	Correct	4008 ms	283396 KB	Output is correct
57	Correct	4290 ms	309452 KB	Output is correct
58	Correct	4526 ms	329532 KB	Output is correct
59	Correct	4770 ms	353612 KB	Output is correct
60	Correct	5035 ms	375972 KB	Output is correct
61	Correct	5302 ms	399772 KB	Output is correct
62	Correct	5493 ms	427344 KB	Output is correct
63	Correct	5950 ms	457924 KB	Output is correct
64	Correct	4169 ms	346960 KB	Output is correct
65	Correct	4105 ms	347012 KB	Output is correct
66	Correct	10778 ms	95980 KB	Output is correct
67	Correct	1381 ms	129952 KB	Output is correct
68	Correct	2292 ms	227040 KB	Output is correct
69	Correct	3142 ms	231292 KB	Output is correct
70	Execution timed out	18026 ms	230324 KB	Time limit exceeded
71	Halted	0 ms	0 KB	-

Submission #563858

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 35.0 / 35.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
35.0 / 35.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 38.0