oj.uz

Submission #599947

# Submission time Handle Problem Language Result Execution time Memory
599947 2022-07-20T10:20:09 Z TimDee Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 250628 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define forn(i,n) for (int i=0; i<n; ++i)
#define pb(x) push_back(x);
#define f first
#define s second

void solve() {
	int n, m; cin>>n>>m;
	vector<pair<int,int>> a(n);
	forn(i,n) cin>>a[i].first>>a[i].second;
	vector<vector<int>> adj(n);
	if (n<=5000) {

		forn(i,n) {
			forn(j,n) {
				if (i==j) continue;
				if (a[j].f<=a[i].s && a[i].s<=a[j].s) adj[i].pb(j);
			}
		}

	} else {

		set<pair<int,int>> s;
		forn(i,n) s.insert({a[i].s,i});

		auto p = s.end(); --p;
		for (;;--p) {
			auto x=*p; int i=x.s;
			auto it = s.upper_bound({a[i].f,-1});
			auto z=*it; if (z.f<a[x.s].f) ++it;
			while (it!=s.end() && (*it).f<=x.f) {
				if ((*it).s!=i) adj[(*it).s].pb(i);
				++it;
			}

			if (p==s.begin()) break;
		}

	}
	
	vector<vector<int>> dp(5000,vector<int>(5000,-1));
	if (n<=5000) {
		forn(i,n) {
			queue<int> q;
			dp[i][i]=0;
			q.push(i);
			vector<int> vis(n,0); vis[i]=1;
			while (!q.empty()) {
				int u=q.front(); q.pop();
				for (auto v:adj[u]) {
					if (!vis[v]) {
						vis[v]|=1;
						dp[i][v]=dp[i][u]+1;
						q.push(v);
					}
				}
			}
		}
	}

	forn(i,m) {
		int u,v; cin>>u>>v;
		--u, --v;
		if (n<=5000) {
			if (dp[u][v]==-1) cout<<"impossible\n";
			else cout<<dp[u][v]<<'\n';
		}
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	solve();
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 196140 KB Output is correct
2 Incorrect 168 ms 203624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 196104 KB Output is correct
2 Correct 77 ms 196200 KB Output is correct
3 Correct 91 ms 196392 KB Output is correct
4 Correct 86 ms 196212 KB Output is correct
5 Correct 88 ms 196300 KB Output is correct
6 Correct 127 ms 197936 KB Output is correct
7 Correct 210 ms 199452 KB Output is correct
8 Correct 255 ms 201604 KB Output is correct
9 Correct 994 ms 204304 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 196104 KB Output is correct
2 Correct 77 ms 196200 KB Output is correct
3 Correct 91 ms 196392 KB Output is correct
4 Correct 86 ms 196212 KB Output is correct
5 Correct 88 ms 196300 KB Output is correct
6 Correct 127 ms 197936 KB Output is correct
7 Correct 210 ms 199452 KB Output is correct
8 Correct 255 ms 201604 KB Output is correct
9 Correct 994 ms 204304 KB Output is correct
10 Correct 82 ms 196160 KB Output is correct
11 Correct 77 ms 196192 KB Output is correct
12 Correct 90 ms 196200 KB Output is correct
13 Correct 83 ms 196296 KB Output is correct
14 Correct 92 ms 196168 KB Output is correct
15 Correct 139 ms 197872 KB Output is correct
16 Correct 214 ms 199520 KB Output is correct
17 Correct 289 ms 201548 KB Output is correct
18 Correct 1006 ms 204304 KB Output is correct
19 Execution timed out 1593 ms 250628 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 196104 KB Output is correct
2 Correct 77 ms 196200 KB Output is correct
3 Correct 91 ms 196392 KB Output is correct
4 Correct 86 ms 196212 KB Output is correct
5 Correct 88 ms 196300 KB Output is correct
6 Correct 127 ms 197936 KB Output is correct
7 Correct 210 ms 199452 KB Output is correct
8 Correct 255 ms 201604 KB Output is correct
9 Correct 994 ms 204304 KB Output is correct
10 Correct 83 ms 196116 KB Output is correct
11 Correct 80 ms 196212 KB Output is correct
12 Correct 93 ms 196180 KB Output is correct
13 Correct 86 ms 196276 KB Output is correct
14 Correct 102 ms 196292 KB Output is correct
15 Correct 125 ms 197860 KB Output is correct
16 Correct 214 ms 199488 KB Output is correct
17 Correct 250 ms 201612 KB Output is correct
18 Correct 1014 ms 204308 KB Output is correct
19 Incorrect 159 ms 203452 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 203516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 196140 KB Output is correct
2 Incorrect 168 ms 203624 KB Output isn't correct
3 Halted 0 ms 0 KB -