Submission #580864

#TimeUsernameProblemLanguageResultExecution timeMemory
580864talant117408Event Hopping (BOI22_events)C++17
10 / 100
1599 ms42624 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define long unsigned long #define pb push_back #define mp make_pair #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define lb lower_bound #define ub upper_bound #define sz(v) int((v).size()) #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl '\n' const int N = 1e5+7; vector <int> graph[N]; int shortest[5003][5003]; int s[N], e[N], n; void bfs(int p) { for (int i = 1; i <= n; i++) { shortest[p][i] = 2e9; } shortest[p][p] = 0; queue <int> K; K.push(p); while (!K.empty()) { auto v = K.front(); K.pop(); for (auto to : graph[v]) { if (shortest[p][to] > shortest[p][v] + 1) { shortest[p][to] = shortest[p][v] + 1; K.push(to); } } } } void solve() { int q; cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> s[i] >> e[i]; } vector <pii> queries(q); for (auto &to : queries) cin >> to.first >> to.second; if (n <= 5000) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) continue; if (s[j] <= e[i] && e[i] <= e[j]) graph[i].pb(j); } } for (int i = 1; i <= n; i++) bfs(i); for (auto to : queries) { if (shortest[to.first][to.second] > 1e9) cout << "impossible" << endl; else cout << shortest[to.first][to.second] << endl; } } } int main() { do_not_disturb int t = 1; //~ cin >> t; while (t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...