이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);
const int N=100010,
INF=1e9;
int n,it;
int uu[N],vv[N];
int a[N],sz[N],d[N],w[N],bit[N],st[N],ed[N],par[N],dep[N],id[N];
vector<int> val;
vector<int> ad[N];
vector<ii> mp[N];
void dfs1(int u){
sz[u]=1;
forv(v,ad[u]){
dep[v]=dep[u]+1;
par[v]=u;
dfs1(v);
sz[u]+=sz[v];
if(sz[d[u]]<sz[v]) d[u]=v;
}
}
void dfs2(int u){
st[u]=++it;
if(!w[u]) w[u]=u;
if(d[u]) w[d[u]]=w[u], dfs2(d[u]);
forv(v,ad[u]) if(v!=d[u]) dfs2(v);
ed[u]=it;
}
vector<int> rev;
void upd(int i,int x){
for(;i<=val.size();i+=i&-i){
bit[i]+=x;
rev.push_back(i);
}
}
int que(int i){
if(i>val.size()) return 0;
int ret=0;
for(;i;i-=i&-i) ret+=bit[i];
return ret;
}
vector<ii> take(int u,int v){ /// take element beginning from v in set_u
/// mp stores elements from leaf to root
int sz=dep[v]-dep[w[u]]+1;
vector<ii> inq;
vector<ii>&val=mp[u];
fordec(j,val.size()-1,0){
if(sz<=val[j].se){
inq.push_back({val[j].fi,sz});
break;
}
sz-=val[j].se;
inq.push_back(val[j]);
}
reverse(all(inq));
return inq;
}
int mode;
void modify(int u,int v,int we){
int sz=dep[v]-dep[w[u]]+1;
vector<ii>&val=mp[u];
for(;;){
if(sz<=val.back().se){
if(sz<val.back().se){
val.back()={val.back().fi,val.back().se-sz};
} else val.pop_back();
break;
}
sz-=val.back().se;
val.pop_back();
}
val.push_back({we,dep[v]-dep[w[u]]+1});
}
main(){
#define task "vim"
//freopen(task".inp","r",stdin);
//freopen(task".out","w",stdout);
forinc(i,1,n=in) val.push_back(a[i]=in);
sort(all(val)), val.erase(unique(all(val)),val.end());
forinc(i,1,n) a[i]=lower_bound(all(val),a[i])-val.begin()+1;
forinc(i,2,n){
uu[i]=in, vv[i]=in;
ad[uu[i]].push_back(vv[i]);
}
dfs1(1);
dfs2(1);
//forinc(i,1,n) cout<<i<<" "<<d[i]<<"\n";
forinc(i,1,n) if(!d[i]){
mp[i].push_back({INF,dep[i]-dep[w[i]]+1});
int j=i;
for(;;){
id[j]=i;
if(j==w[i]) break;
j=par[j];
}
}
forinc(i,2,n){
int p=uu[i], u=vv[i];
vector<int> path;
int j=p;
int tot=0;
while(j){
if(0)
if(i==5){
cerr<<id[j]<<" "<<j<<"\n";
forv(t,take(id[j],j))
cerr<<t.fi<<" "<<t.se<<"\n";
gg
}
forv(t,take(id[j],j)){
//if(i==5)
//cerr<<id[j]<<" "<<j<<"\n";
//cerr<<t.fi<<" "<<t.se<<"\n";
tot+=que(t.fi-1)*t.se;
//if(i==5) cerr<<tot<<"\n";
upd(t.fi,t.se);
}
j=par[w[j]];
}
//if(i==5) gg
cout<<tot<<"\n";
//cerr<<tot<<"\n";
j=u;
while(j){
modify(id[j],j,a[u]);
j=par[w[j]];
}
//if(i==4) gg
forv(j,rev) bit[j]=0;
rev.clear();
if(i==3){
//forv(j,mp[8]) cerr<<j.fi<<" "<<j.se<<"\n";
//gg
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
construction.cpp: In function 'void upd(int, int)':
construction.cpp:54:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;i<=val.size();i+=i&-i){
~^~~~~~~~~~~~
construction.cpp: In function 'int que(int)':
construction.cpp:60:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i>val.size()) return 0;
~^~~~~~~~~~~
construction.cpp: At global scope:
construction.cpp:102:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |