oj.uz

답안 #55063

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55063 2018-07-06T00:15:25 Z spencercompton Railway Trip (JOI17_railway_trip) C++17
30 / 100
 2000 ms 20260 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;
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 540 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 3 ms 564 KB Output is correct
6 Correct 3 ms 564 KB Output is correct
7 Correct 3 ms 564 KB Output is correct
8 Correct 2 ms 564 KB Output is correct
9 Correct 2 ms 596 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 612 KB Output is correct
2 Correct 19 ms 3940 KB Output is correct
3 Correct 18 ms 3940 KB Output is correct
4 Correct 18 ms 3940 KB Output is correct
5 Correct 25 ms 3940 KB Output is correct
6 Correct 21 ms 3940 KB Output is correct
7 Correct 28 ms 4308 KB Output is correct
8 Correct 15 ms 4308 KB Output is correct
9 Execution timed out 2049 ms 4964 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 477 ms 4964 KB Output is correct
2 Correct 413 ms 4964 KB Output is correct
3 Correct 440 ms 4964 KB Output is correct
4 Correct 536 ms 4964 KB Output is correct
5 Correct 638 ms 4964 KB Output is correct
6 Correct 571 ms 4964 KB Output is correct
7 Correct 575 ms 4964 KB Output is correct
8 Correct 379 ms 4964 KB Output is correct
9 Correct 315 ms 4964 KB Output is correct
10 Correct 775 ms 4964 KB Output is correct
11 Correct 922 ms 5972 KB Output is correct
12 Correct 915 ms 7452 KB Output is correct
13 Correct 883 ms 8740 KB Output is correct
14 Correct 804 ms 9988 KB Output is correct
15 Correct 999 ms 11360 KB Output is correct
16 Correct 1096 ms 12736 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1084 ms 12952 KB Output is correct
2 Correct 994 ms 14744 KB Output is correct
3 Correct 908 ms 15976 KB Output is correct
4 Correct 1124 ms 17844 KB Output is correct
5 Correct 411 ms 19752 KB Output is correct
6 Execution timed out 2084 ms 20260 KB Time limit exceeded
7 Halted 0 ms 0 KB -