제출 #972560

#제출 시각아이디문제언어결과실행 시간메모리
972560idasEvent Hopping (BOI22_events)C++11
0 / 100
414 ms52304 KiB
#include <bits/stdc++.h> #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr) #define FOR(i, begin, end) for(int i=(begin); i<(end); i++) #define sz(x) int((x).size()) #define pb push_back #define s second #define f first using namespace std; typedef vector<int> vi; typedef pair<int, int> pii; typedef tuple<int, int, int> tiii; const int INF=1e9; const int N=5e3+10; int n, q, s[N], e[N], d[N][N]; set<tiii> st; void upd_set(int in, int nd, int mn_dist) { auto it=st.lower_bound({in,nd,0}); if(it==st.end()){ st.insert({in,nd,mn_dist}); return; } int a, b, c; tie(a,b,c)=*it; if(a==in && b==nd){ st.erase(it); mn_dist=min(mn_dist, c); } st.insert({in,nd,mn_dist}); } vector<pii> inf; void precalc() { sort(inf.begin(), inf.end(), greater<pii>()); vi vis; while(!inf.empty()){ int now_end=(inf.back()).f; vi ins; while(!inf.empty() && (inf.back()).f==now_end){ pii it=inf.back(); inf.pop_back(); int in=it.s; ins.pb(in); vis.pb(in); st.insert({in,now_end,0}); } for(auto i : ins){ for(auto x : vis){ if(i==x) continue; auto it=st.lower_bound({x,s[i],0}); if(it!=st.end()){ int in, nd, mn_dist; tie(in, nd, mn_dist)=*it; if(in==x){ d[x][i]=min(d[x][i], mn_dist+1); upd_set(in, now_end, d[x][i]); } } } } } } int main() { FAST_IO; cin >> n >> q; FOR(i, 0, n) { cin >> s[i] >> e[i]; inf.pb({e[i],i}); } FOR(i, 0, n) FOR(j, 0, n) if(i!=j) d[i][j]=INF; precalc(); // FOR(i, 0, n) // { // FOR(j, 0, n) // { // cout << i << " " << j << ": " << d[i][j] << '\n'; // } // } while(q--){ int a, b; cin >> a >> b; --a; --b; if(d[a][b]==INF){ cout << "impossible\n"; } else{ cout << d[a][b] << '\n'; } } } /* 2 1 1 4 2 3 1 2 5 2 1 3 2 4 4 7 7 9 3 7 */
#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...