oj.uz

Submission #536786

# Submission time Handle Problem Language Result Execution time Memory
536786 2022-03-14T03:31:26 Z kym Railway Trip 2 (JOI22_ho_t4) C++14
8 / 100
 2000 ms 484440 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) {
				conn[pi(i,j)] = 1;
				continue;
			}
			if(j<i) {
				if(j>=st)conn[pi(i,j)]=1;
			} else {
				if(j<=en)conn[pi(i,j)]=1;
			}
		}
	}
	for(auto i:conn) {
		db2(i.f.f,i.f.s);
		V[i.f.f].pb(i.f.s);
	}
	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 22 ms 32940 KB Output is correct
2 Correct 26 ms 33332 KB Output is correct
3 Correct 43 ms 34952 KB Output is correct
4 Correct 34 ms 34972 KB Output is correct
5 Correct 16 ms 31860 KB Output is correct
6 Correct 73 ms 38728 KB Output is correct
7 Correct 65 ms 38036 KB Output is correct
8 Correct 69 ms 38504 KB Output is correct
9 Correct 71 ms 38376 KB Output is correct
10 Correct 14 ms 31820 KB Output is correct
11 Correct 16 ms 32084 KB Output is correct
12 Correct 16 ms 32164 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32940 KB Output is correct
2 Correct 26 ms 33332 KB Output is correct
3 Correct 43 ms 34952 KB Output is correct
4 Correct 34 ms 34972 KB Output is correct
5 Correct 16 ms 31860 KB Output is correct
6 Correct 73 ms 38728 KB Output is correct
7 Correct 65 ms 38036 KB Output is correct
8 Correct 69 ms 38504 KB Output is correct
9 Correct 71 ms 38376 KB Output is correct
10 Correct 14 ms 31820 KB Output is correct
11 Correct 16 ms 32084 KB Output is correct
12 Correct 16 ms 32164 KB Output is correct
13 Execution timed out 2092 ms 103120 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2092 ms 3052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2124 ms 479436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2122 ms 484440 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32940 KB Output is correct
2 Correct 26 ms 33332 KB Output is correct
3 Correct 43 ms 34952 KB Output is correct
4 Correct 34 ms 34972 KB Output is correct
5 Correct 16 ms 31860 KB Output is correct
6 Correct 73 ms 38728 KB Output is correct
7 Correct 65 ms 38036 KB Output is correct
8 Correct 69 ms 38504 KB Output is correct
9 Correct 71 ms 38376 KB Output is correct
10 Correct 14 ms 31820 KB Output is correct
11 Correct 16 ms 32084 KB Output is correct
12 Correct 16 ms 32164 KB Output is correct
13 Execution timed out 2092 ms 103120 KB Time limit exceeded
14 Halted 0 ms 0 KB -