oj.uz

Submission #29004

# Submission time Handle Problem Language Result Execution time Memory
29004 2017-07-18T05:35:06 Z 김동현(#1169) Railway Trip (JOI17_railway_trip) C++14
20 / 100
 2000 ms 18456 KB 
#include <bits/stdc++.h>
using namespace std;

int n, k, q, md[100010];
vector<int> v[100010], e[100010];
set<int> ss;

void add(int x, int y){
	e[x].push_back(y);
	e[y].push_back(x);
}

int get(int x, int y){
	fill(md + 1, md + n + 1, n);
	md[x] = 0;
	queue<int> q;
	q.push(x);
	while(!q.empty()){
		int c = q.front(); q.pop();
		for(auto &i : e[c]){
			if(md[i] > md[c] + 1){
				md[i] = md[c] + 1;
				q.push(i);
			}
		}
	}
	return md[y];
}

int main(){
	scanf("%d%d%d", &n, &k, &q);
	for(int i = 1, x; i <= n; i++){
		scanf("%d", &x);
		v[x].push_back(i);
	}
	for(int i = 0; i < v[k].size(); i++){
		if(i) add(v[k][i - 1], v[k][i]);
		ss.insert(v[k][i]);
	}
	for(int i = k - 1; i >= 1; i--){
		for(int j = 0, jj; j < v[i].size(); j = jj){
			auto t = ss.lower_bound(v[i][j]);
			auto u = t; u--;
			add(*u, v[i][j]);
			for(jj = j + 1; jj < v[i].size(); jj++){
				auto tt = ss.lower_bound(v[i][jj]);
				if(tt != t) break;
				add(v[i][jj - 1], v[i][jj]);
			}
			add(v[i][jj - 1], *t);
		}
		for(auto &j : v[i]) ss.insert(j);
	}
	for(int x, y; q--; ){
		scanf("%d%d", &x, &y);
		printf("%d\n", get(x, y) - 1);
	}
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:31:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &q);
                             ^
railway_trip.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^
railway_trip.cpp:55:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
                        ^

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7236 KB Output is correct
2 Correct 239 ms 15968 KB Output is correct
3 Correct 346 ms 16004 KB Output is correct
4 Correct 453 ms 15956 KB Output is correct
5 Correct 483 ms 16084 KB Output is correct
6 Correct 553 ms 16080 KB Output is correct
7 Correct 636 ms 17664 KB Output is correct
8 Correct 89 ms 15484 KB Output is correct
9 Correct 119 ms 15948 KB Output is correct
10 Correct 106 ms 15804 KB Output is correct
11 Correct 419 ms 16212 KB Output is correct
12 Correct 456 ms 16080 KB Output is correct
13 Correct 399 ms 15948 KB Output is correct
14 Correct 429 ms 16212 KB Output is correct
15 Correct 453 ms 16080 KB Output is correct
16 Correct 399 ms 15948 KB Output is correct
17 Correct 266 ms 16276 KB Output is correct
18 Correct 283 ms 16332 KB Output is correct
19 Correct 279 ms 18456 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 15748 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 17664 KB Execution timed out
2 Halted 0 ms 0 KB -