# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1036523 | model_code | Petrol stations (CEOI24_stations) | C++17 | 3527 ms | 2097152 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Author: Jiří Kalvoda
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
ll k;
struct Node{
vector<pair<Node*, ll>> e;
pair<Node*, ll> up;
ll counts=0;
int id;
int subtree_size;
vector<ll> dp_here;
vector<ll> dp_after_edge;
int make_rooted(Node * _up)
{
subtree_size=1;
for(int i=0; i<e.size(); i++)
{
if(e[i].first == _up)
{
up = e[i];
e[i] = e[e.size()-1];
e.pop_back();
}
}
for(auto &[nd, l] : e)
subtree_size += nd->make_rooted(this);
return subtree_size;
}
void go()
{
dp_here = vector<ll>(k+1);
dp_after_edge = vector<ll>(k+1);
dp_here[k]+=1;
for(auto &[nd, l] : e)
nd->go();
for(auto &[nd, l] : e)
for (int i=0; i<k+1; i++)
dp_here[i] += nd->dp_after_edge[i];
for (int i=0; i<k+1; i++)
{
if(i-up.second >= 0)
dp_after_edge[i-up.second] += dp_here[i];
else
{
dp_after_edge[k-up.second] += dp_here[i];
counts += dp_here[i]*(n-subtree_size);
}
}
}
void go2(vector<ll> dp_down)
{
for(auto &[nd, l] : e)
{
vector<ll> dp_down_nd = dp_down;
dp_down_nd[k] += 1;
for(auto &[nd2, l2] : e) if(nd != nd2)
for (int i=0; i<k+1; i++)
dp_down_nd[i] += nd2->dp_after_edge[i];
auto dp_down_after_edge = vector<ll>(k+1);
for (int i=0; i<k+1; i++)
{
if(i-l >= 0)
dp_down_after_edge[i-l] += dp_down_nd[i];
else
{
dp_down_after_edge[k-l] += dp_down_nd[i];
counts += dp_down_nd[i]*nd->subtree_size;
}
}
nd->go2(dp_down_after_edge);
}
}
} *nds;
int main(int argc, char ** argv)
{
scanf("%d%lld", &n, &k);
nds = new Node[n];
for (int i=0; i<n; i++) nds[i].id = i;
for (int i=0; i<n-1; i++)
{
int a,b;
ll l;
scanf("%d%d%lld", &a, &b, &l);
nds[a].e.push_back({nds+b, l});
nds[b].e.push_back({nds+a, l});
}
nds[0].make_rooted(NULL);
nds[0].go();
nds[0].go2(vector<ll>(k+1));
for (int i=0; i<n; i++) printf("%lld\n", nds[i].counts);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |