| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 125099 |
2019-07-04T15:30:46 Z |
davitmarg |
Chase (CEOI17_chase) |
C++17 |
|
524 ms |
17184 KB |
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
int n,k,color[100005],used[100005],cnt[100005],c;
LL a[100005],ans;
vector<int> g[100005];
void dfsCnt(int v,int p=0)
{
cnt[v]=1;
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i];
if(used[to] || to==p)
continue;
dfsCnt(to,v);
cnt[v]+=cnt[to];
}
}
int centroid(int v)
{
dfsCnt(v);
c++;
queue<int> q;
q.push(v);
while(!q.empty())
{
int u=q.front();
q.pop();
color[u]=c;
bool can=((cnt[v]-cnt[u])*2<=cnt[v]);
for(int i=0;i<g[u].size();i++)
{
int to=g[u][i];
if(color[to]==c || used[to])
continue;
q.push(to);
if(cnt[to]*2>cnt[v])
can=0;
}
if(can)
{
used[u]=1;
return u;
}
}
}
LL d[4*100005],t[4*100005];
void push(int v,int l,int r,bool f=1)
{
if(d[v]==-1)
return;
if(l!=r)
{
d[v*2]=d[v];
d[v*2+1]=d[v];
if(f)
{
int m=(l+r)/2;
push(v*2,l,m,0);
push(v*2+1,m+1,r,0);
}
}
t[v]=d[v];
d[v]=-1;
}
void build(int v,int l,int r)
{
d[v]=-1;
t[v]=-mod*mod;
if(l==r)
return;
int m=(l+r)/2;
build(v*2,l,m);
build(v*2+1,m+1,r);
}
void update(int v,int l,int r,int pos,LL val)
{
push(v,l,r);
if(l==r)
{
t[v]=max(t[v],val);
return;
}
int m=(l+r)/2;
if(pos<=m)
update(v*2,l,m,pos,val);
else
update(v*2+1,m+1,r,pos,val);
t[v]=max(t[v*2],t[v*2+1]);
}
LL get(int v,int l,int r,int i,int j)
{
if(i>j)
return -mod *mod;
push(v,l,r);
if(l==i && r==j)
return t[v];
int m=(l+r)/2;
return max(
get(v*2,l,m,i,min(m,j)),
get(v*2+1,m+1,r,max(m+1,i),j));
}
vector<pair<LL,int>> upd;
LL start;
void dfs(int v,int p,int depth,LL sum)
{
if(depth>k)
return;
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i];
if(to==p)
continue;
sum+=a[to];
}
LL x=get(1,0,k,0,k-depth+1);
ans=max(ans,x+sum-a[v]-start);
upd.PB(MP(sum,depth));
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i];
if(used[to] || to==p)
continue;
dfs(to,v,depth+1,sum);
}
}
void solve(int v)
{
vector<int> nxt;
start=a[v];
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i];
start+=a[to];
}
d[1]=-mod*mod;
update(1,0,k,0,0);
update(1,0,k,1,start);
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i];
if(used[to])
continue;
upd.clear();
dfs(to,v,2,start);
for(int i=0;i<upd.size();i++)
update(1,0,k,upd[i].second,upd[i].first);
}
ans=max(ans,get(1,0,k,0,k)-a[v]);
reverse(all(g[v]));
d[1]=-mod*mod;
update(1,0,k,0,0);
update(1,0,k,1,start);
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i];
if(used[to])
continue;
upd.clear();
dfs(to,v,2,start);
for(int i=0;i<upd.size();i++)
update(1,0,k,upd[i].second,upd[i].first);
}
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i];
if(used[to])
continue;
solve(centroid(to));
}
}
int main()
{
cin>>n>>k;
build(1,0,n);
for(int i=1;i<=n;i++)
scanf("%lld",a+i);
for(int i=1;i<=n-1;i++)
{
int a,b;
scanf("%d%d",&a,&b);
g[a].PB(b);
g[b].PB(a);
}
solve(centroid(1));
cout<<ans<<endl;
return 0;
}
/*
5 3
1 2 3 4 5
1 2
1 3
3 4
3 5
12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12
*/
Compilation message
chase.cpp: In function 'void dfsCnt(int, int)':
chase.cpp:32:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
chase.cpp: In function 'int centroid(int)':
chase.cpp:54:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[u].size();i++)
~^~~~~~~~~~~~
chase.cpp: In function 'void dfs(int, int, int, long long int)':
chase.cpp:140:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
chase.cpp:151:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
chase.cpp: In function 'void solve(int)':
chase.cpp:164:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
chase.cpp:173:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
chase.cpp:180:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<upd.size();i++)
~^~~~~~~~~~~
chase.cpp:189:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
chase.cpp:196:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<upd.size();i++)
~^~~~~~~~~~~
chase.cpp:200:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
chase.cpp: In function 'int centroid(int)':
chase.cpp:69:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
chase.cpp: In function 'int main()':
chase.cpp:214:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",a+i);
~~~~~^~~~~~~~~~~~
chase.cpp:218:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
524 ms |
17184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
