oj.uz

Submission #105836

# Submission time Handle Problem Language Result Execution time Memory
105836 2019-04-15T10:29:04 Z Pro_ktmr Railway Trip (JOI17_railway_trip) C++14
20 / 100
 498 ms 8940 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2720 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 6 ms 2816 KB Output is correct
5 Correct 5 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 7 ms 2816 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2816 KB Output is correct
2 Correct 321 ms 7824 KB Output is correct
3 Correct 464 ms 8096 KB Output is correct
4 Correct 362 ms 8184 KB Output is correct
5 Correct 378 ms 8432 KB Output is correct
6 Correct 365 ms 8552 KB Output is correct
7 Correct 445 ms 8848 KB Output is correct
8 Correct 184 ms 7504 KB Output is correct
9 Correct 230 ms 7976 KB Output is correct
10 Correct 225 ms 7896 KB Output is correct
11 Correct 340 ms 8156 KB Output is correct
12 Correct 304 ms 8076 KB Output is correct
13 Correct 313 ms 8172 KB Output is correct
14 Correct 275 ms 8040 KB Output is correct
15 Correct 254 ms 8140 KB Output is correct
16 Correct 303 ms 8268 KB Output is correct
17 Correct 498 ms 8940 KB Output is correct
18 Correct 440 ms 8912 KB Output is correct
19 Correct 308 ms 8764 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -