이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
long long a[100005], t[100005], sz[100005], depth[100005], par[100005], heavypar[100005], specialadj[100005], specialpar[100005], seg[400005], cnt;
vector<pair<long long, long long> > vec;
pair<long long, long long> edge[100005];
vector<long long> adj[100005];
void dfs1(long long u)
{
sz[u]=1;
for (long long v:adj[u])
{
depth[v]=depth[u]+1;
dfs1(v);
sz[u]+=sz[v];
}
}
void dfs2(long long u)
{
long long heavy=0;
t[u]=(++cnt);
for (long long v:adj[u])
if (!heavy || sz[heavy]<sz[v])
heavy=v;
if (heavy)
{
heavypar[heavy]=heavypar[u];
dfs2(heavy);
for (long long v:adj[u])
{
if (v==heavy)
continue;
heavypar[v]=v;
dfs2(v);
}
}
}
void push(long long i, long long l, long long r)
{
if (l==r || !seg[i])
return;
seg[i*2]=seg[i*2+1]=seg[i];
seg[i]=0;
}
void upd(long long i, long long l, long long r, long long ql, long long qr, long long x)
{
if (ql<=l && r<=qr)
{
seg[i]=x;
return;
}
push(i, l, r);
long long mid=(l+r)/2;
if (l<=qr && ql<=mid)
upd(i*2, l, mid, ql, qr, x);
if (mid<qr && ql<=r)
upd(i*2+1, mid+1, r, ql, qr, x);
}
long long qry(long long i, long long l, long long r, long long x)
{
if (l==r)
return seg[i];
push(i, l, r);
long long mid=(l+r)/2;
if (x<=mid)
return qry(i*2, l, mid, x);
else
return qry(i*2+1, mid+1, r, x);
}
long long calc(long long l, long long r)
{
/*cout << "calc " << l << ' ' << r << ": ";
for (long long i=l; i<=r; i++)
cout << vec[i].first << 'x' << vec[i].second << ' ';
cout << '\n';*/
if (l==r)
return 0;
long long mid=(l+r)/2, ind=0, sum=0, ans=0;
vector<pair<long long, long long> > vec1, vec2;
for (long long i=l; i<=mid; i++)
vec1.push_back(vec[i]);
for (long long i=mid+1; i<=r; i++)
vec2.push_back(vec[i]);
sort(vec1.begin(), vec1.end());
sort(vec2.begin(), vec2.end());
for (long long i=0; i<vec2.size(); i++)
{
while (ind<vec1.size() && vec1[ind].first<vec2[i].first)
{
sum+=vec1[ind].second;
ind++;
}
ans+=sum*vec2[i].second;
}
return ans+calc(l, mid)+calc(mid+1, r);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n;
cin >> n;
for (long long i=1; i<=n; i++)
cin >> a[i];
for (long long i=1; i<n; i++)
{
long long u, v;
cin >> u >> v;
edge[i]={u, v};
adj[u].push_back(v);
par[v]=u;
}
par[1]=heavypar[1]=1;
dfs1(1);
dfs2(1);
for (long long i=1; i<=n; i++)
{
upd(1, 1, n, t[i], t[i], i);
specialpar[i]=i;
}
for (long long i=1; i<n; i++)
{
long long u=edge[i].first, specialgrp=qry(1, 1, n, t[u]);
//cout << "u specialgrp " << u << ' ' << specialgrp << '\n';
vec.clear();
vec.push_back({a[specialgrp], depth[u]-depth[specialpar[specialgrp]]+1});
u=specialpar[specialgrp];
//long long tmp=0;
while (u!=1)
{
long long v=par[u], w=specialadj[v], specialgrp2=qry(1, 1, n, t[v]);
//tmp++;
//if (tmp<=10)
vec.push_back({a[specialgrp2], depth[u]-depth[specialpar[specialgrp2]]});
//cout << "u v w specialgrp specialgrp2 " << u << ' ' << v << ' ' << w << ' ' << specialgrp << ' ' << specialgrp2 << '\n';
specialadj[v]=u;
u=specialpar[specialgrp]=specialpar[specialgrp2];
specialpar[specialgrp2]=w;
}
cout << calc(0, vec.size()-1) << '\n';
u=edge[i].first;
long long v=heavypar[u];
upd(1, 1, n, t[v], t[u], edge[i].second);
while (v!=1)
{
//cout << "u v " << u << ' ' << v << '\n';
u=par[v];
v=heavypar[u];
upd(1, 1, n, t[v], t[u], edge[i].second);
}
u=edge[i].second, v=edge[i].first;
if (specialadj[v])
{
long long w=specialadj[v], specialgrp2=qry(1, 1, n, t[w]);
specialpar[specialgrp2]=w;
}
specialadj[v]=u;
specialpar[u]=1;
/*for (long long j=1; j<=n; j++)
cout << qry(1, 1, n, t[j]) << ' ';
cout << '\n';
for (long long j=1; j<=n; j++)
cout << specialadj[j] << ' ';
cout << '\n';
for (long long j=1; j<=n; j++)
cout << specialpar[j] << ' ';
cout << '\n';*/
}
}
컴파일 시 표준 에러 (stderr) 메시지
construction.cpp: In function 'long long int calc(long long int, long long int)':
construction.cpp:85:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (long long i=0; i<vec2.size(); i++)
| ~^~~~~~~~~~~~
construction.cpp:87:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | while (ind<vec1.size() && vec1[ind].first<vec2[i].first)
| ~~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |