| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1039670 |
2024-07-31T07:21:29 Z |
정희우(#10993) |
Petrol stations (CEOI24_stations) |
C++17 |
|
618 ms |
77772 KB |
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
using lint = long long;
using intp = pair<int,int>;
using vint = vector<int>;
using vlint = vector<lint>;
using lntp = pair<lint,lint>;
using pqpll = priority_queue<lntp>;
const int MAX_N=70010;
struct Edge
{
int v;
lint d;
};
int n;
lint k;
vector<Edge> edge[MAX_N];
int sz[MAX_N];
int lock[MAX_N];
lint ans[MAX_N];
int fillsz(int v,int p)
{
sz[v]=1;
for(auto e : edge[v])
if(e.v!=p && lock[e.v]==0)
sz[v]+=fillsz(e.v,v);
return sz[v];
}
int findc(int v,int p,int h)
{
for(auto e : edge[v])
if(e.v!=p && lock[e.v]==0 && sz[e.v]>h)
return findc(e.v,v,h);
return v;
}
struct Cent
{
int tsz;
int pn;
vlint px;
vlint seg;
vector<Edge> sube;
vector<vector<lntp>> sub;
void init_()
{
sort(px.begin(),px.end());
pn=unique(px.begin(),px.end())-px.begin()-1;
px.resize(pn+1);
seg.resize(pn<<2);
}
int fp(lint x)
{
return lower_bound(px.begin(),px.end(),x)-px.begin();
}
void update_(int i,int s,int e,int x,lint v)
{
if(s>x || e<=x)return;
if(s==x && x+1==e)
{
seg[i]+=v;
return;
}
update_(i<<1,s,(s+e)>>1,x,v);
update_(i<<1|1,(s+e)>>1,e,x,v);
seg[i]=seg[i<<1]+seg[i<<1|1];
}
lint find_(int i,int s,int e,int l,int r)
{
if(s>=r || e<=l)return 0;
if(l<=s && e<=r)return seg[i];
return find_(i<<1,s,(s+e)>>1,l,r)+find_(i<<1|1,(s+e)>>1,e,l,r);
}
void filld(int v,int p,lint ds,lint d)
{
if(ds<=k)px.push_back(-ds);
px.push_back(ds-d-k);
px.push_back(ds-k);
px.push_back(ds-d);
for(auto e : edge[v])
if(e.v!=p && lock[e.v]==0)
filld(e.v,v,ds+e.d,e.d);
}
pqpll* calcup(int v,int p,lint ds,lint d)
{
pqpll *pq=NULL,*comp=NULL;
for(auto e : edge[v])
if(e.v!=p && lock[e.v]==0)
{
comp=calcup(e.v,v,ds+e.d,e.d);
if(pq==NULL || pq->size()<comp->size())swap(pq,comp);
while(comp!=NULL && !comp->empty())
{
pq->push(comp->top());
comp->pop();
}
if(comp!=NULL)
free(comp);
}
if(pq==NULL)pq=new pqpll;
lint cnt=0;
while(!pq->empty() && pq->top().first>ds-d+k)
{
cnt+=pq->top().second;
pq->pop();
}
ans[v]+=cnt*(tsz-sz[v]);
pq->push({ds,cnt+1});
return pq;
}
void calcdown(int v,int p,lint ds,lint d)
{
lint s=find_(1,0,pn,fp(ds-d-k),fp(ds-k));
ans[p]+=s*sz[v];
update_(1,0,pn,fp(ds-d),s);
for(auto e : edge[v])
if(e.v!=p && lock[e.v]==0)
calcdown(e.v,v,ds+e.d,e.d);
update_(1,0,pn,fp(ds-d),-s);
}
void calc(int v)
{
fillsz(v,v);
filld(v,v,0,0);
init_();
tsz=sz[v];
for(auto e : edge[v])
if(lock[e.v]==0)
{
sube.push_back(e);
pqpll *pq=calcup(e.v,v,e.d,e.d);
sub.push_back({});
while(!pq->empty())
{
sub.back().push_back(pq->top());
pq->pop();
}
free(pq);
for(auto p : sub.back())
update_(1,0,pn,fp(-p.first),p.second);
}
for(int i=0;i<sube.size();i++)
{
auto e=sube[i];
for(auto p : sub[i])
update_(1,0,pn,fp(-p.first),-p.second);
calcdown(e.v,v,e.d,e.d);
for(auto p : sub[i])
update_(1,0,pn,fp(-p.first),p.second);
}
}
};
Cent cent[MAX_N];
void f(int v)
{
fillsz(v,v);
v=findc(v,v,sz[v]/2);
cent[v].calc(v);
lock[v]=1;
for(auto e : edge[v])
if(lock[e.v]==0)
f(e.v);
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> k;
for(int i=1;i<n;i++)
{
int u,v;
lint d;
cin >> u >> v >> d;
edge[u].push_back({v,d});
edge[v].push_back({u,d});
}
f(0);
for(int i=0;i<n;i++)
cout << ans[i] << '\n';
return 0;
}
Compilation message
Main.cpp: In member function 'void Cent::calc(int)':
Main.cpp:151:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for(int i=0;i<sube.size();i++)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10072 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
10076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10072 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
10076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10076 KB |
Output is correct |
| 2 |
Incorrect |
618 ms |
77772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10072 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
10076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10072 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
10076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10072 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
10076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10072 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
10076 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
