oj.uz

Submission #536787

# Submission time Handle Problem Language Result Execution time Memory
536787 2022-03-14T03:32:34 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];
map<pi,bool> conn;
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) {
				V[i].pb(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 31956 KB Output is correct
2 Correct 21 ms 32092 KB Output is correct
3 Correct 33 ms 32340 KB Output is correct
4 Correct 24 ms 32444 KB Output is correct
5 Correct 15 ms 31868 KB Output is correct
6 Correct 51 ms 33052 KB Output is correct
7 Correct 45 ms 32896 KB Output is correct
8 Correct 50 ms 32968 KB Output is correct
9 Correct 62 ms 33004 KB Output is correct
10 Correct 16 ms 31800 KB Output is correct
11 Correct 16 ms 31828 KB Output is correct
12 Correct 15 ms 31828 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31956 KB Output is correct
2 Correct 21 ms 32092 KB Output is correct
3 Correct 33 ms 32340 KB Output is correct
4 Correct 24 ms 32444 KB Output is correct
5 Correct 15 ms 31868 KB Output is correct
6 Correct 51 ms 33052 KB Output is correct
7 Correct 45 ms 32896 KB Output is correct
8 Correct 50 ms 32968 KB Output is correct
9 Correct 62 ms 33004 KB Output is correct
10 Correct 16 ms 31800 KB Output is correct
11 Correct 16 ms 31828 KB Output is correct
12 Correct 15 ms 31828 KB Output is correct
13 Execution timed out 2094 ms 42400 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1387 ms 2984 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 870 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 791 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 31956 KB Output is correct
2 Correct 21 ms 32092 KB Output is correct
3 Correct 33 ms 32340 KB Output is correct
4 Correct 24 ms 32444 KB Output is correct
5 Correct 15 ms 31868 KB Output is correct
6 Correct 51 ms 33052 KB Output is correct
7 Correct 45 ms 32896 KB Output is correct
8 Correct 50 ms 32968 KB Output is correct
9 Correct 62 ms 33004 KB Output is correct
10 Correct 16 ms 31800 KB Output is correct
11 Correct 16 ms 31828 KB Output is correct
12 Correct 15 ms 31828 KB Output is correct
13 Execution timed out 2094 ms 42400 KB Time limit exceeded
14 Halted 0 ms 0 KB -