Submission #587609

#TimeUsernameProblemLanguageResultExecution timeMemory
587609cfalasEvent Hopping (BOI22_events)C++17
10 / 100
1578 ms41336 KiB
#include<bits/stdc++.h> using namespace std; #define mp make_pair #define INF 10000000 #define MOD 1000000007 #define MID ((l+r)/2) #define HASHMOD 2305843009213693951 #define ll long long #define ull unsigned long long #define F first #define S second typedef pair<ll, ll> ii; typedef pair<ii, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef map<int, int> mii; #define EPS 1e-6 #define FOR(i,n) for(int i=0;i<((int)(n));i++) #define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++) #define FOA(v, a) for(auto v : a) int t, n; vi a, b; vector<vi> adj; int ans[5500][5500]; int main(){ int q; cin>>n>>q; adj.assign(n+1, vi()); vii e(n); FOR(i,n){ cin>>e[i].F>>e[i].S; } FOR(i,n){ FOR(j,n){ if(i==j) continue; if(e[j].F<=e[i].S && e[i].S<=e[j].S){ adj[i+1].push_back(j+1); } } /* cout<<i+1<<": "; FOA(v, adj[i+1]) cout<<v<<" "; cout<<endl; */ } FORi(i,1,n+1){ priority_queue<ii> q; q.push({0, i}); FOR(j,n+1) ans[i][j] = MOD; ans[i][i] = 0; while(!q.empty()){ ii t = q.top(); q.pop(); if(-t.F > ans[i][t.S]) continue; FOA(v, adj[t.S]){ if(ans[i][v] > 1 - t.F){ ans[i][v] = 1 - t.F; q.push({-ans[i][v], v}); } } } } while(q--){ int a, b; cin>>a>>b; if(ans[a][b] < MOD) cout<<ans[a][b]<<endl; else cout<<"impossible\n"; } }
#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...