oj.uz

Submission #536788

# Submission time Handle Problem Language Result Execution time Memory
536788 2022-03-14T03:34:00 Z kym Railway Trip 2 (JOI22_ho_t4) C++14
8 / 100
 2000 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
#define int ll 
#define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i)
#define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#define reach 
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long 
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <ll, ll> pi;
typedef tuple<ll,ll,ll> ti3;
typedef tuple<ll,ll,ll,ll> ti4;
ll rand(ll a, ll b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (ll)1e18 + 500;
template <typename T> void chmax(T& a, const T b) { a=max(a,b); }
template <typename T> void chmin(T& a, const T b) { a=min(a,b); }
const int MAXN = -1;
int dist[2005][2005];
int n,k,m;
pi A[2005];
vector<int> V[2005];
int32_t main() 
{
	IAMSPEED
	cin >> n >> k >> m;
	FOR(i,1,m) {
		cin >> A[i].f >> A[i].s;
	}
	FOR(i,1,n) {
		int en=0,st=n+1;
		FOR(x,1,m) {
			if(A[x].f < A[x].s) {
				if(A[x].f <= i && A[x].f + k - 1 >= i)chmax(en,A[x].s);
			} else {
				if(A[x].f-k+1 <= i && A[x].f >= i)chmin(st,A[x].s);
			}
		}
		//we get min and max for this start point.
		FOR(j,1,n) {
			if(i==j) {
				continue;
			}
			if(j<i) {
				if(j>=st)V[i].pb(j);
			} else {
				if(j<=en)V[i].pb(j);
			}
		}
	}

	memset(dist,-1,sizeof dist);
	FOR(i,1,n) {
		queue<int> q;
		dist[i][i] = 0;
		for(q.push(i);q.size();q.pop()) {
			int x = q.front();
			for(auto v:V[x]){
				if(dist[i][v] == -1 || dist[i][v]  > dist[i][x] + 1) {
					dist[i][v] = dist[i][x] + 1;
					q.push(v);
				}
			}
		}
	}
	int Q; cin >> Q;
	while(Q--) {
		int a,b; cin >> a >> b;
		cout << dist[a][b] << '\n';
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31940 KB Output is correct
2 Correct 29 ms 32076 KB Output is correct
3 Correct 32 ms 32340 KB Output is correct
4 Correct 25 ms 32400 KB Output is correct
5 Correct 16 ms 31780 KB Output is correct
6 Correct 48 ms 32980 KB Output is correct
7 Correct 44 ms 32980 KB Output is correct
8 Correct 47 ms 32980 KB Output is correct
9 Correct 50 ms 33012 KB Output is correct
10 Correct 14 ms 31828 KB Output is correct
11 Correct 20 ms 31784 KB Output is correct
12 Correct 20 ms 31908 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31940 KB Output is correct
2 Correct 29 ms 32076 KB Output is correct
3 Correct 32 ms 32340 KB Output is correct
4 Correct 25 ms 32400 KB Output is correct
5 Correct 16 ms 31780 KB Output is correct
6 Correct 48 ms 32980 KB Output is correct
7 Correct 44 ms 32980 KB Output is correct
8 Correct 47 ms 32980 KB Output is correct
9 Correct 50 ms 33012 KB Output is correct
10 Correct 14 ms 31828 KB Output is correct
11 Correct 20 ms 31784 KB Output is correct
12 Correct 20 ms 31908 KB Output is correct
13 Execution timed out 2060 ms 42380 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1372 ms 2920 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 862 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 784 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31940 KB Output is correct
2 Correct 29 ms 32076 KB Output is correct
3 Correct 32 ms 32340 KB Output is correct
4 Correct 25 ms 32400 KB Output is correct
5 Correct 16 ms 31780 KB Output is correct
6 Correct 48 ms 32980 KB Output is correct
7 Correct 44 ms 32980 KB Output is correct
8 Correct 47 ms 32980 KB Output is correct
9 Correct 50 ms 33012 KB Output is correct
10 Correct 14 ms 31828 KB Output is correct
11 Correct 20 ms 31784 KB Output is correct
12 Correct 20 ms 31908 KB Output is correct
13 Execution timed out 2060 ms 42380 KB Time limit exceeded
14 Halted 0 ms 0 KB -