Submission #888914

#TimeUsernameProblemLanguageResultExecution timeMemory
888914vjudge1Passport (JOI23_passport)C++17
6 / 100
60 ms59016 KiB
#include <bits/stdc++.h> #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast,unroll-loops") using namespace std; #define pb push_back #define int long long #define f first #define s second #define pii pair<int,int> const int mod= 1e9 +7; const int N=2505; vector<vector<int>> dist(N, vector<int> (N, mod)); void solve(){ int n,m,k; cin>>n; if(n<=2505){ vector<int>l(n+1),r(n+1); for(int i = 0;i<n;i++){ int a,b; cin>>l[i]>>r[i]; l[i]--;r[i]--; } int h,x; cin>>h>>x; x--; priority_queue <pair<int,pii>, vector <pair<int,pii>>, greater <pair<int,pii>> > q; q.push({1,{l[x],r[x]}}); dist[l[x]][r[x]] = 1; int ml = -1,mr = -1; while(!q.empty()){ auto [w,t] = q.top(); int x = t.f,y = t.s; q.pop(); if(dist[x][y]<w)continue; int ml = x;int mr = y; for(int i = x;i<=y;i++){ ml = min(ml,l[i]); mr = max(mr,r[i]); } if(x<y){ if(dist[ml][y]>dist[x][y] + 1){ dist[ml][y] = dist[x][y] + 1; q.push({dist[ml][y],{ml,y}}); } if(dist[x][mr]>dist[x][y] + 1){ dist[x][mr] = dist[x][y] + 1; q.push({dist[x][mr],{x,mr}}); } if(dist[x+1][y-1]>dist[x][y]){ dist[x+1][y-1] = dist[x][y]; q.push({dist[x+1][y-1],{x+1,y-1}}); } // dist[x][mr] = dist[x][y] + 1; } else if(x==y){ if(dist[l[x]][r[x]]>dist[x][y] + 1){ dist[l[x]][r[x]] = dist[x][y] + 1; q.push({dist[l[x]][r[x]],{l[x],r[x]}}); } } } if(dist[0][n-1]==mod)cout<<-1<<"\n"; else cout<<dist[0][n-1]<<"\n"; } else{ vector<pii>v;vector<int>pref(n+1,0); int r1 = 1; int cnt = 1; for(int i = 0;i<n;i++){ int l,r; cin>>l>>r; v.pb({l,r}); if(i==0)r1 = r; if(i==n)cout<<"Baiysh want a rulet!!!!!!!!!!!!!!!!!!!!!!\n"; else{ pref[i+1] = max(pref[i],r); } } int last = -1;int ans = 1; while(r1!=n){ last = r1; r1 = pref[r1]; ans++; if(last==r1){ cout<<-1<<"\n"; exit(0); } } cout<<ans<<"\n"; } } signed main() { // freopen("seq.in", "r", stdin); // freopen("seq.out", "w", stdout); ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); int cnt=0; int tt=1; while(tt--)solve(); }

Compilation message (stderr)

passport.cpp: In function 'void solve()':
passport.cpp:24:8: warning: unused variable 'a' [-Wunused-variable]
   24 |    int a,b;
      |        ^
passport.cpp:24:10: warning: unused variable 'b' [-Wunused-variable]
   24 |    int a,b;
      |          ^
passport.cpp:37:7: warning: unused variable 'ml' [-Wunused-variable]
   37 |   int ml = -1,mr = -1;
      |       ^~
passport.cpp:37:15: warning: unused variable 'mr' [-Wunused-variable]
   37 |   int ml = -1,mr = -1;
      |               ^~
passport.cpp:81:6: warning: unused variable 'cnt' [-Wunused-variable]
   81 |  int cnt = 1;
      |      ^~~
passport.cpp:16:8: warning: unused variable 'm' [-Wunused-variable]
   16 |  int n,m,k;
      |        ^
passport.cpp:16:10: warning: unused variable 'k' [-Wunused-variable]
   16 |  int n,m,k;
      |          ^
passport.cpp: In function 'int main()':
passport.cpp:118:6: warning: unused variable 'cnt' [-Wunused-variable]
  118 |  int cnt=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...