oj.uz

Submission #126542

# Submission time Handle Problem Language Result Execution time Memory
126542 2019-07-08T03:41:13 Z baluteshih Railway Trip (JOI17_railway_trip) C++14
20 / 100
 2000 ms 8156 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()]) 
			G[i].pb(st.back()),G[st.back()].pb(i),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 110 ms 7340 KB Output is correct
3 Correct 108 ms 7288 KB Output is correct
4 Correct 123 ms 7512 KB Output is correct
5 Correct 124 ms 7416 KB Output is correct
6 Correct 143 ms 7676 KB Output is correct
7 Correct 145 ms 7928 KB Output is correct
8 Correct 65 ms 6776 KB Output is correct
9 Correct 65 ms 7288 KB Output is correct
10 Correct 60 ms 7032 KB Output is correct
11 Correct 106 ms 7416 KB Output is correct
12 Correct 105 ms 7388 KB Output is correct
13 Correct 110 ms 7384 KB Output is correct
14 Correct 107 ms 7440 KB Output is correct
15 Correct 108 ms 7416 KB Output is correct
16 Correct 110 ms 7536 KB Output is correct
17 Correct 164 ms 8028 KB Output is correct
18 Correct 144 ms 7928 KB Output is correct
19 Correct 91 ms 7928 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 7544 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 2051 ms 8156 KB Time limit exceeded
2 Halted 0 ms 0 KB -