Submission #55064

#	Time	Username	Problem	Language	Result	Execution time	Memory
55064		spencercompton	Railway Trip (JOI17_railway_trip)	C++17	45 / 100	2076 ms	4928 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, k, q;
	cin >> n >> k >> q;
	if(q<=50){
	int ar[n];
	vector<pair<int, int> > li;
	for(int i = 0; i<n; i++){
		cin >> ar[i];
	}
	int left[n];
	left[0] = 0;
	li.push_back(make_pair(ar[0],0));
	for(int i=  1; i<n; i++){
		while(li[(int)li.size()-1].first<ar[i]){
			li.pop_back();
		}
		left[i] = li[(int)li.size()-1].second;
		li.push_back(make_pair(ar[i],i));
	}
	li.clear();
	int right[n];
	right[n-1] = n-1;
	li.push_back(make_pair(ar[n-1],n-1));
	for(int i = n-2; i>=0; i--){
		while(li[(int)li.size()-1].first<ar[i]){
			li.pop_back();
		}
		right[i] = li[(int)li.size()-1].second;
		li.push_back(make_pair(ar[i],i));
	}
	for(int i = 0; i<q; i++){
		int s, t;
		cin >> s >> t;
		s--;
		t--;
		int dist1[n];
		int dist2[n];
		int inf = n+2;
		for(int j = 0; j<n; j++){
			dist1[j] = inf;
			dist2[j] = inf;
		}
		vector<int> li1;
		dist1[s] = 0;
		li1.push_back(s);
		for(int j = 0; j<li1.size(); j++){
			int now = li1[j];
			if(dist1[left[now]]==inf){
				dist1[left[now]] = dist1[now]+1;
				li1.push_back(left[now]);
			}
			if(dist1[right[now]]==inf){
				dist1[right[now]] = dist1[now]+1;
				li1.push_back(right[now]);
			}
		}
		vector<int> li2;
		dist2[t] = 0;
		li2.push_back(t);
		for(int j = 0; j<li2.size(); j++){
			int now = li2[j];
			if(dist2[left[now]]==inf){
				dist2[left[now]] = dist2[now]+1;
				li2.push_back(left[now]);
			}
			if(dist2[right[now]]==inf){
				dist2[right[now]] = dist2[now]+1;
				li2.push_back(right[now]);
			}
		}
		int ans = inf;
		for(int i = 0; i<n; i++){
			ans = min(ans,dist1[i] + dist2[i] - 1);
		}
		cout << ans << endl;
	}
	return 0;
	}
	int ar[n];
	vector<pair<int, int> > li;
	for(int i = 0; i<n; i++){
		cin >> ar[i];
	}
	int left[n];
	int dl[n];
	dl[0] = 0;
	left[0] = 0;
	li.push_back(make_pair(ar[0],0));
	int cnt[k+1];
	int ind[n];
	ind[0] = 0;
	for(int i = 0; i<=k; i++){
		cnt[i] = 0;
	}
	cnt[ar[0]] = 1;
	for(int i=  1; i<n; i++){
		ind[i] = cnt[ar[i]];
		cnt[ar[i]]++;
		while(li[(int)li.size()-1].first<ar[i]){
			li.pop_back();
		}
		if(li[(int)li.size()-1].first==ar[i]){
			dl[i] = dl[li[(int)li.size()-1].second]+1;
			li.pop_back();
		}
		else{
			dl[i] = 1;
		}
		if(ar[i]==k){
			left[i] = i;
			dl[i] = 0;
		}
		else{
			left[i] = li[(int)li.size()-1].second;
		}
		li.push_back(make_pair(ar[i],i));
	}
	li.clear();
	int right[n];
	int dr[n];
	dr[n-1] = 0;
	right[n-1] = n-1;
	li.push_back(make_pair(ar[n-1],n-1));
	for(int i = n-2; i>=0; i--){
		while(li[(int)li.size()-1].first<ar[i]){
			li.pop_back();
		}
		if(li[(int)li.size()-1].first==ar[i]){
			dr[i] = dr[li[(int)li.size()-1].second]+1;
			li.pop_back();
		}
		else{
			dr[i] = 1;
		}
		if(ar[i]==k){
			right[i] = i;
			dr[i] =0 ;
		}
		else{
			right[i] = li[(int)li.size()-1].second;
		}
		
		li.push_back(make_pair(ar[i],i));
	}
	int dist1[n];
	int dist2[n];
	bool v1[n];
	bool v2[n];
	int inf = n+2;
	for(int j = 0; j<n; j++){
		dist1[j] = inf;
		dist2[j] = inf;
		v1[j] = false;
		v2[j] = false;
	}
	for(int i = 0; i<q; i++){
		int s, t;
		cin >> s >> t;
		s--;
		t--;
		vector<int> li1;
		dist1[s] = 0;
		priority_queue<pair<int, int> > pq1;
		pq1.push(make_pair(0,s));
		while(pq1.size()>0){
			// cout << "Z " << endl;
			pair<int, int> now = pq1.top();
			// cout << now.first << " " << now.second << endl;
			pq1.pop();
			if(v1[now.second]){
				continue;
			}
			// cout << "A " << now.second << " " << -now.first << endl;
			dist1[now.second] = -now.first;
			v1[now.second] = true;
			li1.push_back(now.second);
			// cout << now.second << " -> " << left[now.second] << endl;
			// cout << now.second << " -> R " << right[now.second] << endl;
			pq1.push(make_pair(now.first-dl[now.second],left[now.second]));
			pq1.push(make_pair(now.first-dr[now.second],right[now.second]));
		}
		// cout << "X " << endl;
		vector<int> li2;
		dist2[t] = 0;
		priority_queue<pair<int, int> > pq2;
		pq2.push(make_pair(0,t));
		while(pq2.size()>0){
			pair<int, int> now = pq2.top();
			pq2.pop();
			if(v2[now.second]){
				continue;
			}
			li2.push_back(now.second);
			// cout << "B " << now.second << " " << -now.first << endl;
			dist2[now.second] = -now.first;
			v2[now.second] = true;
			pq2.push(make_pair(now.first-dl[now.second],left[now.second]));
			pq2.push(make_pair(now.first-dr[now.second],right[now.second]));
		}
		int ans = inf;
		for(int i = 0; i<li1.size(); i++){
			for(int j = 0; j<li2.size(); j++){
				int a = li1[i];
				int b = li2[j];
				if(a>b){
					swap(a,b);
				}
				if(ar[a]==ar[b]){
					// cout << "QWERTY " << a << " " << b << endl;
					if(ar[a]==k || left[b]<a){
						int best = ind[a]-ind[b];
						if(best<0){
							best = -best;
						}
						int here = dist1[li1[i]]+dist2[li2[j]]+best-1;
						// cout << a << " " << b << " # " << here << endl;
						// cout << "OK " << dist1[a] << " " << dist2[b] << " " << best << " " << cnt[ar[a]]-best << endl;
						ans = min(here,ans);
					}
				}
			}
		}
		for(int i = 0; i<li1.size(); i++){
			int x = li1[i];
			v1[x] = false;
			dist1[x] = inf;
		}
		for(int i = 0; i<li2.size(); i++){
			int x = li2[i];
			v2[x] = false;
			dist2[x] = inf;
		}
		cout << ans << endl;
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 0 / 55