oj.uz

Submission #599950

# Submission time Handle Problem Language Result Execution time Memory
599950 2022-07-20T10:24:28 Z TimDee Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 250700 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) {
		bitset<5000> vis;
		forn(i,n) {
			vis.reset();
			queue<int> q;
			dp[i][i]=0;
			q.push(i);
			vis.set(i);
			while (!q.empty()) {
				int u=q.front(); q.pop();
				for (auto v:adj[u]) {
					if (!vis[v]) {
						vis.set(v);
						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 1 ms 212 KB Output is correct
2 Incorrect 204 ms 203480 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 15 ms 8136 KB Output is correct
5 Correct 20 ms 8148 KB Output is correct
6 Correct 57 ms 9812 KB Output is correct
7 Correct 164 ms 11464 KB Output is correct
8 Correct 202 ms 13524 KB Output is correct
9 Correct 1086 ms 16256 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 15 ms 8136 KB Output is correct
5 Correct 20 ms 8148 KB Output is correct
6 Correct 57 ms 9812 KB Output is correct
7 Correct 164 ms 11464 KB Output is correct
8 Correct 202 ms 13524 KB Output is correct
9 Correct 1086 ms 16256 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 19 ms 8148 KB Output is correct
13 Correct 13 ms 8148 KB Output is correct
14 Correct 19 ms 8148 KB Output is correct
15 Correct 55 ms 9812 KB Output is correct
16 Correct 172 ms 11460 KB Output is correct
17 Correct 228 ms 13552 KB Output is correct
18 Correct 1063 ms 16252 KB Output is correct
19 Execution timed out 1590 ms 250700 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 15 ms 8136 KB Output is correct
5 Correct 20 ms 8148 KB Output is correct
6 Correct 57 ms 9812 KB Output is correct
7 Correct 164 ms 11464 KB Output is correct
8 Correct 202 ms 13524 KB Output is correct
9 Correct 1086 ms 16256 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 18 ms 8260 KB Output is correct
13 Correct 12 ms 8148 KB Output is correct
14 Correct 19 ms 8232 KB Output is correct
15 Correct 56 ms 9812 KB Output is correct
16 Correct 175 ms 11472 KB Output is correct
17 Correct 192 ms 13568 KB Output is correct
18 Correct 1113 ms 16252 KB Output is correct
19 Incorrect 184 ms 203408 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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