oj.uz

Submission #72711

# Submission time Handle Problem Language Result Execution time Memory
72711 2018-08-26T18:52:48 Z ikura355 Railway Trip (JOI17_railway_trip) C++14
20 / 100
 2000 ms 20616 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
const int inf = 1e9;

int n,k,m;
int a[maxn];
int st[maxn], ft[maxn];

int dq[maxn], len[maxn];
vector<int> way[maxn];
queue<int> q;

void init() {
	int sz = 0;
	for(int x=1;x<=n;x++) {
		int l = 1, r = sz, mid, pos = -1;
		while(l<=r) {
			mid = (l+r)/2;
			if(a[x] <= a[dq[mid]]) {
				pos = dq[mid];
				l = mid+1;
			}
			else r = mid-1;
		}
		if(pos!=-1) {
			way[pos].push_back(x);
			way[x].push_back(pos);
//			printf("%d - %d\n",x,pos);
		}
		dq[++sz] = x;
		while(sz>=2 && a[dq[sz-1]] <= a[dq[sz]]) dq[sz-1] = dq[sz], sz--;
	}
	sz = 0;
	for(int x=n;x>=1;x--) {
		int l = 1, r = sz, mid, pos = -1;
		while(l<=r) {
			mid = (l+r)/2;
			if(a[x] <= a[dq[mid]]) {
				pos = dq[mid];
				l = mid+1;
			}
			else r = mid-1;
		}
		if(pos!=-1) {
			way[pos].push_back(x);
			way[x].push_back(pos);
//			printf("%d - %d\n",x,pos);
		}
		dq[++sz] = x;
		while(sz>=2 && a[dq[sz-1]] <= a[dq[sz]]) dq[sz-1] = dq[sz], sz--;
	}
}
int solve(int x, int y) {
	for(int i=1;i<=n;i++) len[i] = inf;
	len[x] = 0;
	q.push(x);
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(auto v : way[u]) {
			if(len[v] > len[u] + 1) {
				len[v] = len[u] + 1;
				q.push(v);
			}
		}
	}
	return len[y] - 1;
}
int main() {
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d%d",&st[i],&ft[i]);
	init();
	for(int i=1;i<=m;i++) printf("%d\n",solve(st[i],ft[i]));
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&k,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~
railway_trip.cpp:72:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
                        ~~~~~^~~~~~~~~~~~
railway_trip.cpp:73:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%d%d",&st[i],&ft[i]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 6 ms 2852 KB Output is correct
4 Correct 4 ms 2852 KB Output is correct
5 Correct 6 ms 2968 KB Output is correct
6 Correct 7 ms 3060 KB Output is correct
7 Correct 4 ms 3060 KB Output is correct
8 Correct 4 ms 3060 KB Output is correct
9 Correct 6 ms 3060 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3060 KB Output is correct
2 Correct 207 ms 8312 KB Output is correct
3 Correct 278 ms 8796 KB Output is correct
4 Correct 275 ms 8952 KB Output is correct
5 Correct 241 ms 9340 KB Output is correct
6 Correct 222 ms 9644 KB Output is correct
7 Correct 333 ms 10284 KB Output is correct
8 Correct 92 ms 10284 KB Output is correct
9 Correct 102 ms 11440 KB Output is correct
10 Correct 102 ms 11440 KB Output is correct
11 Correct 219 ms 11916 KB Output is correct
12 Correct 219 ms 12652 KB Output is correct
13 Correct 246 ms 13220 KB Output is correct
14 Correct 227 ms 13680 KB Output is correct
15 Correct 208 ms 14392 KB Output is correct
16 Correct 266 ms 14852 KB Output is correct
17 Correct 266 ms 15656 KB Output is correct
18 Correct 247 ms 16260 KB Output is correct
19 Correct 158 ms 16260 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 18688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 20616 KB Time limit exceeded
2 Halted 0 ms 0 KB -