oj.uz

Submission #729451

# Submission time Handle Problem Language Result Execution time Memory
729451 2023-04-24T07:25:39 Z Sam_a17 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 42840 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif

#define sz(x) (int)x.size()
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt __builtin_popcount

#define pb push_back
#define popf pop_front
#define popb pop_back
#define ld long double
#define ll long long

void print(long long t) { cerr << t; }
void print(int t) { cerr << t; }
void print(string t) { cerr << t; }
void print(char t) { cerr << t; }
void print(double t) { cerr << t; }
void print(long double t) { cerr << t; }
void print(unsigned long long t) { cerr << t; }

template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[], V n) { cerr << "["; for (int i = 0; i < n; i++) { print(v[i]); cerr << " "; } cerr << "]"; }
template <class T, class V> void print(pair <T, V> p) { cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}"; }
template <class T> void print(vector <T> v) { cerr << "[ "; for (T i : v) { print(i); cerr << " "; } cerr << "]"; }
template <class T> void print(set <T> v) { cerr << "[ "; for (T i : v) { print(i); cerr << " "; } cerr << "]"; }
template <class T> void print(multiset <T> v) { cerr << "[ "; for (T i : v) { print(i); cerr << " "; } cerr << "]"; }
template <class T, class V> void print(map <T, V> v) { cerr << "[ "; for (auto i : v) { print(i); cerr << " "; } cerr << "]"; }
template <class T, class V> void print(unordered_map <T, V> v) { cerr << "[ "; for (auto i : v) { print(i); cerr << " "; } cerr << "]"; }
template <class T> void print(deque <T> v) { cerr << "[ "; for (T i : v) { print(i); cerr << " "; } cerr << "]"; }

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'

// for random generations
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 myrand(131);

// for grid problems
int dx[8] = { -1,0,1,0,1,-1,1,-1 };
int dy[8] = { 0,1,0,-1,1,1,-1,-1 };

// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
	fastIO();

	if (str == "input") {
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	}
	else {
		// freopen("skis.in", "r", stdin);
		// freopen("skis.out", "w", stdout);
	}
}
// Indexed Set  
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 10, M = 5e3 + 10, inf = 1e8;
vector<int> adj[N];
int n, q, l[N], r[N];
int dist[M][M];

void bfs(int node) {
	queue<int> q;
	q.push(node);
	vector<bool> vis(n + 1);
	vis[node] = true;
	for(int i = 1; i <= n; i++) {
		dist[node][i] = inf;
	}
	dist[node][node] = 0;

	while(!q.empty()) {
		auto u = q.front();
		q.pop();

		for(auto i: adj[u]) {
			if(vis[i]) continue;
			dist[node][i] = dist[node][u] + 1;
			vis[i] = true;
			q.push(i);
		}
	}
}

void solve_() {
	cin >> n >> q;

	for(int i = 1; i <= n; i++) {
		cin >> l[i] >> r[i];
	}

	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(i == j) continue;
			if(r[i] >= l[j] && r[i] <= r[j]) {
				adj[i].push_back(j);
			}
		}
	}

	for(int i = 1; i <= n; i++) {
		bfs(i);
	}

	while(q--) {
		int x, y; cin >> x >> y;
		if(dist[x][y] == inf) {
			cout << "impossible" << '\n';
		} else {
			cout << dist[x][y] << '\n';
		}
	}

}

int main() {
	setIO();

	auto solve = [&](int test_case)-> void {
		for (int i = 1; i <= test_case; i++) {
			solve_();
		}
	};

	int test_cases = 1;
	// cin >> test_cases;
	solve(test_cases);

	return 0;
}

Compilation message

events.cpp: In function 'void setIO(std::string)':
events.cpp:69:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:70:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   freopen("output.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1570 ms 8296 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 20 ms 12972 KB Output is correct
4 Correct 16 ms 13012 KB Output is correct
5 Correct 21 ms 13000 KB Output is correct
6 Correct 73 ms 13796 KB Output is correct
7 Correct 192 ms 14564 KB Output is correct
8 Correct 226 ms 15588 KB Output is correct
9 Correct 1205 ms 16964 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 20 ms 12972 KB Output is correct
4 Correct 16 ms 13012 KB Output is correct
5 Correct 21 ms 13000 KB Output is correct
6 Correct 73 ms 13796 KB Output is correct
7 Correct 192 ms 14564 KB Output is correct
8 Correct 226 ms 15588 KB Output is correct
9 Correct 1205 ms 16964 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 5032 KB Output is correct
12 Correct 20 ms 12920 KB Output is correct
13 Correct 15 ms 13028 KB Output is correct
14 Correct 21 ms 13012 KB Output is correct
15 Correct 59 ms 13768 KB Output is correct
16 Correct 189 ms 14516 KB Output is correct
17 Correct 235 ms 15580 KB Output is correct
18 Correct 1291 ms 16944 KB Output is correct
19 Execution timed out 1563 ms 42840 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 20 ms 12972 KB Output is correct
4 Correct 16 ms 13012 KB Output is correct
5 Correct 21 ms 13000 KB Output is correct
6 Correct 73 ms 13796 KB Output is correct
7 Correct 192 ms 14564 KB Output is correct
8 Correct 226 ms 15588 KB Output is correct
9 Correct 1205 ms 16964 KB Output is correct
10 Correct 4 ms 4948 KB Output is correct
11 Correct 3 ms 5024 KB Output is correct
12 Correct 19 ms 13020 KB Output is correct
13 Correct 16 ms 13012 KB Output is correct
14 Correct 20 ms 12948 KB Output is correct
15 Correct 57 ms 13748 KB Output is correct
16 Correct 174 ms 14564 KB Output is correct
17 Correct 230 ms 15584 KB Output is correct
18 Correct 1044 ms 17056 KB Output is correct
19 Execution timed out 1546 ms 7908 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1570 ms 8296 KB Time limit exceeded
3 Halted 0 ms 0 KB -