結果
問題 | No.1868 Teleporting Cyanmond |
ユーザー |
|
提出日時 | 2022-01-07 16:26:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 159 ms / 2,000 ms |
コード長 | 1,703 bytes |
コンパイル時間 | 2,996 ms |
コンパイル使用メモリ | 221,984 KB |
最終ジャッジ日時 | 2025-01-27 09:01:43 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include<bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define FOR(i,n) for(int i = 0; i < (n); i++) #define sz(c) ((int)(c).size()) #define ten(x) ((int)1e##x) #define all(v) (v).begin(), (v).end() using namespace std; using ll=long long; using FLOW=int; using P = pair<ll,ll>; const long double PI=acos(-1); const ll INF=1e18; const int inf=1e9; template<typename T> struct SegmentTree{ using F=function<T(T,T)>; F fT; const T et; int n; vector<T> dat; SegmentTree(int N,F fT_,T et_) : fT(fT_),et(et_){ n=1; while(n<N)n*=2; dat.assign(2*n-1,et_); } void add(int k,T x){ k+=n-1; dat[k]+=x; while(k){ k=(k-1)/2; dat[k]=fT(dat[k*2+1],dat[k*2+2]); } } void apply(int k,T x){ k+=n-1; dat[k]=fT(dat[k],x); while(k){ k=(k-1)/2; dat[k]=fT(dat[k*2+1],dat[k*2+2]); } } void update(int k,T x){ k+=n-1; dat[k]=x; while(k){ k=(k-1)/2; dat[k]=fT(dat[k*2+1],dat[k*2+2]); } } T query(int l,int r){ return query_sub(l,r,0,0,n); } T query_sub(int l,int r,int k=0,int a=0,int b=-1){ if(b<0)b=n; if(r<=a || b<=l)return et; if(l<=a && b<=r)return dat[k]; return fT(query_sub(l,r,k*2+1,a,(a+b)/2),query_sub(l,r,k*2+2,(a+b)/2,b)); } }; auto f = [](ll x1,ll x2) -> ll { return min(x1,x2); }; const ll e=INF; int main(){ int n; cin>>n; map<int,set<int>> mp; for(int i=0;i<n-1;i++){ int r; cin>>r; mp[r].insert(i+1); } SegmentTree<ll> dp(n+1,f,e); dp.update(1,0); for(int i=1;i<=n;i++){ for(auto l : mp[i]){ dp.apply(i,dp.query(l,i)+1); } } cout<<dp.query(n,n+1)<<endl; }