Submission #105836

#	Time	Username	Problem	Language	Result	Execution time	Memory
105836		Pro_ktmr	Railway Trip (JOI17_railway_trip)	C++14	20 / 100	498 ms	8940 KiB

railway_trip

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair

struct SegmentTree{
private:
	int N;
	vector<int> node;
public:
	void init(int n){
		N = 1;
		while(N < n) N *= 2;
		N = N*2-1;
		node.clear();
		for(int i=0; i<N; i++) node.push_back(0);
	}
	void update(int a, int x){
		int k = a + (N-1)/2;
		node[k] = x;
		while(k > 0){
			k = (k-1) / 2;
			node[k] = max(node[2*k+1], node[2*k+2]);
		}
	}
	int findL(int a, int b, int x, int k=0, int l=0, int r=-1){
		if(r == -1) r = (N+1)/2;
		if(r <= a || b <= l) return INT_MAX;
		if(r-l == 1 && node[k] > x) return k - (N-1)/2;
		else if(r-l == 1) return INT_MAX;
		if(a <= l && r <= b){
			if(node[2*k+1] > x) return findL(a, b, x, 2*k+1, l, (l+r)/2);
			else if(node[2*k+2] > x) return findL(a, b, x, 2*k+2, (l+r)/2, r);
			else return INT_MAX;
		}
		else{
			return min(findL(a, b, x, 2*k+1, l, (l+r)/2), findL(a, b, x, 2*k+2, (l+r)/2, r));
		}
	}
	int findR(int a, int b, int x, int k=0, int l=0, int r=-1){
		if(r == -1) r = (N+1)/2;
		if(r <= a || b <= l) return INT_MIN;
		if(r-l == 1 && node[k] > x) return k - (N-1)/2;
		else if(r-l == 1) return INT_MIN;
		if(a <= l && r <= b){
			if(node[2*k+2] > x) return findR(a, b, x, 2*k+2, (l+r)/2, r);
			else if(node[2*k+1] > x) return findR(a, b, x, 2*k+1, l, (l+r)/2);
			else return INT_MIN;
		}
		else{
			return max(findR(a, b, x, 2*k+1, l, (l+r)/2), findR(a, b, x, 2*k+2, (l+r)/2, r));
		}
	}
	void print(){
		for(int i=0; i<N; i++) cout << node[i] << " ";
		cout << endl;
	}
};

int N,K,Q;
int sta[100000];
SegmentTree st;
vector<int> edge[100000];
int main(){
	cin >> N >> K >> Q;
	if(Q <= 50){
		st.init(N);
		for(int i=0; i<N; i++){
			cin >> sta[i];
			st.update(i, sta[i]);
		}
		//st.print();
		
		//
		
		for(int i=0; i<N; i++){
			int m = 0;
			int idx = i;
			while(true){
				idx = st.findL(idx+1, N, m);
				//cout << "1. " << idx << endl;
				if(idx == INT_MAX) break;
				edge[i].push_back(idx);
				m = sta[idx];
				if(sta[idx] >= sta[i]) break;
			}
			
			m = 0;
			idx = i;
			while(true){
				idx = st.findR(0, idx, m);
				//cout << "2. " << idx << endl;
				if(idx == INT_MIN) break;
				edge[i].push_back(idx);
				m = sta[idx];
				if(sta[idx] >= sta[i]) break;
			}
			
			//for(int j=0; j<edge[i].size(); j++) cout << edge[i][j] << " ";
			//cout << endl;
		}
		
		//
		
		for(int q=0; q<Q; q++){
			int A,B;
			cin >> A >> B;
			A--; B--;
			bool already[100000] = {};
			queue<pair<int,int> > que;
			que.push(MP(A,0));
			already[A] = true;
			while(!que.empty()){
				int now = que.front().first;
				int c = que.front().second;
				//cout << now << " " << c << endl;
				que.pop();
				if(now == B){
					cout << c-1 << endl;
					break;
				}
				for(int i=0; i<edge[now].size(); i++){
					if(already[edge[now][i]]) continue;
					already[edge[now][i]] = true;
					que.push(MP(edge[now][i], c+1));
				}
			}
		}
	}
	else if(K <= 20){
		
	}
	
	return 0;
}

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