Submission #943768

#TimeUsernameProblemLanguageResultExecution timeMemory
943768tmarcinkeviciusEvent Hopping (BOI22_events)C++14
10 / 100
1589 ms414808 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t typedef pair<int,int> pii; typedef vector<int> vii; #define MP make_pair #define PB push_back #define f first #define s second #define INF 2e18 #define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define all(x) (x).begin(), (x).end() #define sz(x) ((ll)(x).size()) struct Interval { int id; pii range; }; int N, Q; vector<Interval> intervals; vector<pii> queries; vector<vector<Interval>> adjSorted; vector<set<int>> adjAll; int32_t main() { //fast_io(); cin >> N >> Q; intervals = vector<Interval>(N + 1); adjAll = vector<set<int>>(N + 1); adjSorted = vector<vector<Interval>>(N + 1); //vector<pii> endPoints; // { time, 0 for start / 1 for end } for (int i = 1; i <= N; i++) { Interval inter; cin >> inter.range.f >> inter.range.s; inter.id = i; intervals[i] = inter; //endPoints.push_back({inter.range.f, 0}); //endPoints.push_back({inter.range.s, 1}); } queries = vector<pii>(Q); for (int i = 0; i < Q; i++) { cin >> queries[i].f >> queries[i].s; } //sort(all(endPoints)); //sort(all(intervals), [](Interval a, Interval b) // { return a.range.s < b.range.s; }); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (i == j) continue; if (intervals[i].range.s >= intervals[j].range.f && intervals[i].range.s <= intervals[j].range.s) { adjAll[i].insert(j); } } } for (int i = 1; i <= N; i++) { int bestE = -1; int bestId = -1; //cout << "adjAll[" << i << "]: {"; for (int j : adjAll[i]) { //cout << j << " "; adjSorted[i].push_back(intervals[j]); } //cout << "}\n"; sort(all(adjSorted[i]), [](Interval a, Interval b) { return a.range.s < b.range.s; }); } for (int q = 0; q < Q; q++) { if (queries[q].f == queries[q].s) { cout << 0 << '\n'; continue; } vector<int> dis(N + 1, INF); queue<int> qu; qu.push(queries[q].f); dis[queries[q].f] = 0; bool impossible = true; while (!qu.empty()) { int fr = qu.front(); qu.pop(); //cout << "at: " << fr << '\n'; if (adjAll[fr].count(queries[q].s)) { //cout << "can go already\n"; cout << dis[fr] + 1 << '\n'; impossible = false; break; } if (adjSorted[fr].size() == 0) { continue; } int low = 0; int high = adjSorted[fr].size() - 1; while (low < high) { //cout << "(" << low << " " << high << ")\n"; int mid = low + (high - low + 1) / 2; if (adjSorted[fr][mid].range.s <= intervals[queries[q].s].range.s) { low = mid; } else { high = mid - 1; } } Interval bestNode = adjSorted[fr][low]; if (bestNode.range.s <= intervals[queries[q].s].range.s && dis[bestNode.id] == INF) { dis[bestNode.id] = dis[fr] + 1; qu.push(bestNode.id); } } if (impossible) { cout << "impossible\n"; } } }

Compilation message (stderr)

events.cpp: In function 'int32_t main()':
events.cpp:86:13: warning: unused variable 'bestE' [-Wunused-variable]
   86 |         int bestE = -1;
      |             ^~~~~
events.cpp:87:13: warning: unused variable 'bestId' [-Wunused-variable]
   87 |         int bestId = -1;
      |             ^~~~~~
#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...