oj.uz

Submission #599949

# Submission time Handle Problem Language Result Execution time Memory
599949 2022-07-20T10:22:48 Z TimDee Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 250604 KB 
#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#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(min(n,5000ll),vector<int>(min(n,5000ll),-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';
		} else {

		}
	}
}

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 0 ms 212 KB Output is correct
2 Incorrect 185 ms 203408 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 18 ms 8148 KB Output is correct
4 Correct 12 ms 8148 KB Output is correct
5 Correct 19 ms 8148 KB Output is correct
6 Correct 56 ms 9812 KB Output is correct
7 Correct 144 ms 11476 KB Output is correct
8 Correct 165 ms 13652 KB Output is correct
9 Correct 905 ms 16252 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 18 ms 8148 KB Output is correct
4 Correct 12 ms 8148 KB Output is correct
5 Correct 19 ms 8148 KB Output is correct
6 Correct 56 ms 9812 KB Output is correct
7 Correct 144 ms 11476 KB Output is correct
8 Correct 165 ms 13652 KB Output is correct
9 Correct 905 ms 16252 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 20 ms 8148 KB Output is correct
13 Correct 14 ms 8184 KB Output is correct
14 Correct 19 ms 8200 KB Output is correct
15 Correct 63 ms 9796 KB Output is correct
16 Correct 160 ms 11480 KB Output is correct
17 Correct 187 ms 13516 KB Output is correct
18 Correct 957 ms 16268 KB Output is correct
19 Execution timed out 1584 ms 250604 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 18 ms 8148 KB Output is correct
4 Correct 12 ms 8148 KB Output is correct
5 Correct 19 ms 8148 KB Output is correct
6 Correct 56 ms 9812 KB Output is correct
7 Correct 144 ms 11476 KB Output is correct
8 Correct 165 ms 13652 KB Output is correct
9 Correct 905 ms 16252 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 17 ms 8272 KB Output is correct
13 Correct 14 ms 8272 KB Output is correct
14 Correct 18 ms 8148 KB Output is correct
15 Correct 60 ms 9828 KB Output is correct
16 Correct 169 ms 11368 KB Output is correct
17 Correct 168 ms 13640 KB Output is correct
18 Correct 868 ms 16256 KB Output is correct
19 Incorrect 176 ms 203468 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 185 ms 203408 KB Output isn't correct
3 Halted 0 ms 0 KB -