제출 #1048126

#제출 시각아이디문제언어결과실행 시간메모리
1048126Maite_Morale밀림 점프 (APIO21_jumps)C++17
23 / 100
718 ms132804 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define vll vector<ll> #define MAX 500005 #define pll pair<ll,ll> #define oo 10000000000000 #define F first #define S second const ll bts=20; pll p[MAX],s[bts+10][MAX],t[bts+10][MAX]; vll v[MAX]; ll d[MAX],N; pll query(ll x,ll y){ if(x>y)return {0,N}; ll c=log2l(abs(x-y)+1); return max(t[c][x],t[c][y-(1LL<<c)+1]); } void dfs(ll x,ll y){ d[x]=d[y]+1; for(auto w : v[x])dfs(w,x); } void init(int n, std::vector<int> h) { h.push_back(oo); stack<ll> s1;s1.push(n); for(int i=0;i<n;i++){ while(h[i]>h[s1.top()]){ p[s1.top()].S=i; s1.pop(); } p[i].F=s1.top(); s1.push(i); } while(!s1.empty()){p[s1.top()].S=n;s1.pop();} s[0][n]={n,n}; for(int i=0;i<n;i++){ s[0][i].F=max(pll {h[p[i].F],p[i].F},pll {h[p[i].S],p[i].S}).S; s[0][i].S=min(pll {h[p[i].F],p[i].F},pll {h[p[i].S],p[i].S}).S; v[s[0][i].S].push_back(i); if(p[i].F==n)p[i].F=-1; //cout<<p[i].F<<" "; }///cout<<"\n"; dfs(n,n); for(int i=1;i<=bts;i++){ for(int j=0;j<=n;j++){ s[i][j].F=s[i-1][s[i-1][j].F].F; s[i][j].S=s[i-1][s[i-1][j].S].S; //if(i==20)cout<<d[j]<<" "; //else cout<<s[i][j].S<<" "; }//cout<<"\n"; } } int minimum_jumps(int A, int B, int C, int D) { swap(B,C); //cout<<A<<" "<<B<<"\n"; if(A<=p[B].F)return -1; //cout<<A<<" "<<B<<"\n"; ll r=0; for(int i=bts;i>=0;i--){ if(d[s[i][A].F]>=d[B]){ r+=(1LL<<i); A=s[i][A].F; } } for(int i=bts;i>=0;i--){ if(d[s[i][A].S]>=d[B]){ r+=(1LL<<i); A=s[i][A].S; } } return r; }

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:7:12: warning: overflow in conversion from 'long int' to 'std::vector<int>::value_type' {aka 'int'} changes value from '10000000000000' to '1316134912' [-Woverflow]
    7 | #define oo 10000000000000
      |            ^~~~~~~~~~~~~~
jumps.cpp:25:17: note: in expansion of macro 'oo'
   25 |     h.push_back(oo);
      |                 ^~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...