oj.uz

Submission #126513

# Submission time Handle Problem Language Result Execution time Memory
126513 2019-07-08T02:42:13 Z baluteshih Railway Trip (JOI17_railway_trip) C++14
20 / 100
 2000 ms 8688 KB 
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define ET cout << "\n"
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

vector<int> G[100005];
int val[100005];
vector<int> st;
queue<int> qu;
int dis[100005];

int main()
{jizz
	int n,k,q,a,b;
	cin >> n >> k >> q;
	for(int i=1;i<=n;++i)
		cin >> val[i];
	for(int i=1;i<=n;++i)
	{
		while(!st.empty()&&val[i]>val[st.back()]) st.pop_back();
		if(!st.empty())
			if(val[st.back()]==val[i])
				G[i].pb(st.back()),G[st.back()].pb(i),st.back()=i;
			else
				G[i].pb(st.back()),G[st.back()].pb(i),st.pb(i);
		else
			st.pb(i);
	}
	st.clear();
	for(int i=n;i>0;--i)
	{
		while(!st.empty()&&val[i]>val[st.back()]) st.pop_back();
		if(!st.empty())
			if(val[st.back()]==val[i])
				G[i].pb(st.back()),G[st.back()].pb(i),st.back()=i;
			else
				G[i].pb(st.back()),G[st.back()].pb(i),st.pb(i);
		else
			st.pb(i);
	}
	while(q--)
	{
		cin >> a >> b,fill(dis+1,dis+n+1,n+1);
		while(!qu.empty()) qu.pop();
		qu.push(a),dis[a]=0;
		while(!qu.empty())
		{
			int u=qu.front();
			qu.pop();
			if(u==b) break;
			for(int i:G[u])
				if(dis[i]>dis[u]+1)
					dis[i]=dis[u]+1,qu.push(i);
		}
		cout << dis[b]-1 << "\n";
	}
}

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 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 139 ms 8084 KB Output is correct
3 Correct 118 ms 8204 KB Output is correct
4 Correct 133 ms 8056 KB Output is correct
5 Correct 129 ms 8056 KB Output is correct
6 Correct 137 ms 8184 KB Output is correct
7 Correct 149 ms 8584 KB Output is correct
8 Correct 68 ms 6776 KB Output is correct
9 Correct 77 ms 8060 KB Output is correct
10 Correct 69 ms 7508 KB Output is correct
11 Correct 120 ms 8312 KB Output is correct
12 Correct 118 ms 8464 KB Output is correct
13 Correct 126 ms 8184 KB Output is correct
14 Correct 119 ms 8408 KB Output is correct
15 Correct 121 ms 8312 KB Output is correct
16 Correct 116 ms 8312 KB Output is correct
17 Correct 156 ms 8520 KB Output is correct
18 Correct 147 ms 8568 KB Output is correct
19 Correct 93 ms 7928 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2033 ms 8440 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 2053 ms 8688 KB Time limit exceeded
2 Halted 0 ms 0 KB -