結果
問題 | No.1524 Upward Mobility |
ユーザー |
![]() |
提出日時 | 2021-05-05 12:37:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,378 ms / 6,000 ms |
コード長 | 4,224 bytes |
コンパイル時間 | 10,386 ms |
コンパイル使用メモリ | 274,456 KB |
最終ジャッジ日時 | 2025-01-21 07:13:16 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:209:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 209 | scanf("%d",&p); | ~~~~~^~~~~~~~~ main.cpp:218:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 218 | scanf("%d",&a[i]); | ~~~~~^~~~~~~~~~~~ main.cpp:221:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 221 | rep(i,N)scanf("%lld",&b[i]); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000000 int N; vector<vector<int>> E; vector<int> a; vector<long long> b; vector<int> sz; struct Data{ long long v = 0;; bool f = false; }; Data op(Data a,Data b){ if(a.f==false)return b; if(b.f==false)return a; if(a.v>b.v)return a; return b; } Data e(){ return Data(); } Data mapping(long long a,Data b){ if(b.f)b.v += a; return b; } long long composition(long long a,long long b){ return a+b; } long long id(){ return 0; } using Segtree = lazy_segtree<Data,op,e,long long,mapping,composition,id>; vector<vector<int>> ps; vector<Segtree> seg; void dfs0(int cur){ sz[cur] = 1; rep(i,E[cur].size()){ int to = E[cur][i]; dfs0(to); sz[cur] += sz[to]; } sort(E[cur].rbegin(),E[cur].rend(),[&](int a,int b){ return sz[a]<sz[b]; }); } void dfs1(int cur,vector<int> &t){ if(t.size()==0){ queue<int> Q; Q.push(cur); t.push_back(N); while(Q.size()>0){ int u = Q.front(); Q.pop(); t.push_back(a[u]); rep(i,E[u].size()){ int to = E[u][i]; Q.push(to); } } sort(t.begin(),t.end()); } rep(i,E[cur].size()){ int to = E[cur][i]; if(i==0){ dfs1(to,t); } else{ t.resize(0); dfs1(to,t); } } if(E[cur].size()==0){ ps[cur] = t; seg[cur] = Segtree(t.size()); } } void dfs2(int cur){ if(E[cur].size()==0){ int d = distance(ps[cur].begin(),lower_bound(ps[cur].begin(),ps[cur].end(),a[cur])); seg[cur].set(d,{b[cur],true}); seg[cur].set(ps[cur].size()-1,{0,true}); return; } if(E[cur].size()==1){ int to = E[cur][0]; dfs2(to); swap(ps[cur],ps[to]); swap(seg[cur],seg[to]); int d = distance(ps[cur].begin(),lower_bound(ps[cur].begin(),ps[cur].end(),a[cur])); seg[cur].set(d,{seg[cur].prod(d+1,ps[cur].size()).v+b[cur],true}); return; } rep(i,E[cur].size()){ int to = E[cur][i]; dfs2(to); } vector<int> pp; rep(i,E[cur].size()){ if(i==0)continue; int to = E[cur][i]; rep(j,ps[to].size()){ pp.push_back(ps[to][j]); } } pp.push_back(a[cur]); sort(pp.begin(),pp.end()); pp.erase(unique(pp.begin(),pp.end()),pp.end()); vector<long long> imos(pp.size(),0LL); rep(i,E[cur].size()){ if(i==0)continue; int to = E[cur][i]; rep(j,ps[to].size()){ int d0; if(j!=0)d0 = distance(pp.begin(),lower_bound(pp.begin(),pp.end(),ps[to][j-1])); else d0 = -1; int d1 = distance(pp.begin(),lower_bound(pp.begin(),pp.end(),ps[to][j])); long long v = seg[to].prod(j,ps[to].size()).v; imos[d1] += v; if(d0>=0)imos[d0] -= v; } } for(int i=imos.size()-1;i>=1;i--){ imos[i-1] += imos[i]; } vector<long long> nv; rep(i,pp.size()){ long long D = imos[i]; int to = E[cur][0]; int d = distance(ps[to].begin(),upper_bound(ps[to].begin(),ps[to].end(),pp[i])); D += seg[to].prod(d,ps[to].size()).v; if(pp[i]==a[cur])D += b[cur]; nv.push_back(D); } /* cout<<cur<<endl; rep(i,pp.size()){ cout<<pp[i]<<','<<nv[i]<<endl; } */ swap(seg[cur],seg[E[cur][0]]); swap(ps[cur],ps[E[cur][0]]); rep(i,E[cur].size()){ if(i==0)continue; int to = E[cur][i]; rep(j,ps[to].size()){ int d0; if(j!=0) d0 = distance(ps[cur].begin(),lower_bound(ps[cur].begin(),ps[cur].end(),ps[to][j-1])); else d0 = 0; int d1 = distance(ps[cur].begin(),lower_bound(ps[cur].begin(),ps[cur].end(),ps[to][j])); long long v = seg[to].prod(j,ps[to].size()).v; seg[cur].apply(d0,d1,v); } } rep(i,pp.size()){ int d = distance(ps[cur].begin(),lower_bound(ps[cur].begin(),ps[cur].end(),pp[i])); seg[cur].set(d,{nv[i],true}); } //cout<<cur<<','<<seg[cur].all_prod()<<endl; } int main(){ cin>>N; E.resize(N); rep(i,N-1){ int p; scanf("%d",&p); p--; E[p].push_back(i+1); } a.resize(N); b.resize(N); rep(i,N){ scanf("%d",&a[i]); a[i]--; } rep(i,N)scanf("%lld",&b[i]); //cout<<'a'<<endl; sz.resize(N); dfs0(0); //cout<<'a'<<endl; seg.resize(N); ps.resize(N); vector<int> t; dfs1(0,t); //cout<<'a'<<endl; dfs2(0); //cout<<seg[0].get(1).v<<endl; cout<<seg[0].all_prod().v<<endl; return 0; }