oj.uz

Submission #55064

# Submission time Handle Problem Language Result Execution time Memory
55064 2018-07-06T00:17:08 Z spencercompton Railway Trip (JOI17_railway_trip) C++17
45 / 100
 2000 ms 4928 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 372 KB Output is correct
3 Correct 3 ms 448 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 544 KB Output is correct
9 Correct 2 ms 544 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 548 KB Output is correct
2 Correct 39 ms 2796 KB Output is correct
3 Correct 36 ms 2796 KB Output is correct
4 Correct 34 ms 2796 KB Output is correct
5 Correct 36 ms 2796 KB Output is correct
6 Correct 34 ms 2796 KB Output is correct
7 Correct 34 ms 2796 KB Output is correct
8 Correct 143 ms 4784 KB Output is correct
9 Correct 92 ms 4784 KB Output is correct
10 Correct 88 ms 4784 KB Output is correct
11 Correct 90 ms 4784 KB Output is correct
12 Correct 92 ms 4784 KB Output is correct
13 Correct 95 ms 4784 KB Output is correct
14 Correct 94 ms 4784 KB Output is correct
15 Correct 88 ms 4784 KB Output is correct
16 Correct 84 ms 4784 KB Output is correct
17 Correct 38 ms 4784 KB Output is correct
18 Correct 36 ms 4784 KB Output is correct
19 Correct 50 ms 4784 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 4784 KB Output is correct
2 Correct 525 ms 4784 KB Output is correct
3 Correct 536 ms 4784 KB Output is correct
4 Correct 444 ms 4784 KB Output is correct
5 Correct 455 ms 4784 KB Output is correct
6 Correct 496 ms 4784 KB Output is correct
7 Correct 519 ms 4784 KB Output is correct
8 Correct 314 ms 4784 KB Output is correct
9 Correct 440 ms 4784 KB Output is correct
10 Correct 847 ms 4784 KB Output is correct
11 Correct 814 ms 4784 KB Output is correct
12 Correct 803 ms 4784 KB Output is correct
13 Correct 748 ms 4784 KB Output is correct
14 Correct 935 ms 4784 KB Output is correct
15 Correct 1240 ms 4784 KB Output is correct
16 Correct 1026 ms 4784 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 938 ms 4784 KB Output is correct
2 Correct 1189 ms 4804 KB Output is correct
3 Correct 1094 ms 4804 KB Output is correct
4 Correct 1066 ms 4804 KB Output is correct
5 Correct 375 ms 4928 KB Output is correct
6 Execution timed out 2076 ms 4928 KB Time limit exceeded
7 Halted 0 ms 0 KB -