oj.uz

Submission #599948

# Submission time Handle Problem Language Result Execution time Memory
599948 2022-07-20T10:21:46 Z TimDee Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 250620 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(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';
		} 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 95 ms 196172 KB Output is correct
2 Incorrect 178 ms 203496 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 75 ms 196132 KB Output is correct
2 Correct 76 ms 196124 KB Output is correct
3 Correct 94 ms 196200 KB Output is correct
4 Correct 83 ms 196368 KB Output is correct
5 Correct 90 ms 196240 KB Output is correct
6 Correct 129 ms 197916 KB Output is correct
7 Correct 212 ms 199420 KB Output is correct
8 Correct 245 ms 201676 KB Output is correct
9 Correct 994 ms 204420 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 196132 KB Output is correct
2 Correct 76 ms 196124 KB Output is correct
3 Correct 94 ms 196200 KB Output is correct
4 Correct 83 ms 196368 KB Output is correct
5 Correct 90 ms 196240 KB Output is correct
6 Correct 129 ms 197916 KB Output is correct
7 Correct 212 ms 199420 KB Output is correct
8 Correct 245 ms 201676 KB Output is correct
9 Correct 994 ms 204420 KB Output is correct
10 Correct 73 ms 196172 KB Output is correct
11 Correct 74 ms 196140 KB Output is correct
12 Correct 105 ms 196228 KB Output is correct
13 Correct 95 ms 196212 KB Output is correct
14 Correct 90 ms 196304 KB Output is correct
15 Correct 127 ms 197872 KB Output is correct
16 Correct 213 ms 199524 KB Output is correct
17 Correct 254 ms 201708 KB Output is correct
18 Correct 1006 ms 204304 KB Output is correct
19 Execution timed out 1567 ms 250620 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 196132 KB Output is correct
2 Correct 76 ms 196124 KB Output is correct
3 Correct 94 ms 196200 KB Output is correct
4 Correct 83 ms 196368 KB Output is correct
5 Correct 90 ms 196240 KB Output is correct
6 Correct 129 ms 197916 KB Output is correct
7 Correct 212 ms 199420 KB Output is correct
8 Correct 245 ms 201676 KB Output is correct
9 Correct 994 ms 204420 KB Output is correct
10 Correct 79 ms 196172 KB Output is correct
11 Correct 83 ms 196172 KB Output is correct
12 Correct 92 ms 196296 KB Output is correct
13 Correct 91 ms 196296 KB Output is correct
14 Correct 107 ms 196260 KB Output is correct
15 Correct 134 ms 197860 KB Output is correct
16 Correct 208 ms 199500 KB Output is correct
17 Correct 289 ms 201632 KB Output is correct
18 Correct 939 ms 204364 KB Output is correct
19 Incorrect 166 ms 203432 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 196172 KB Output is correct
2 Incorrect 178 ms 203496 KB Output isn't correct
3 Halted 0 ms 0 KB -