Submission #1036523

#TimeUsernameProblemLanguageResultExecution timeMemory
1036523model_codePetrol stations (CEOI24_stations)C++17
38 / 100
3527 ms2097152 KiB
// 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)

Main.cpp: In member function 'int Node::make_rooted(Node*)':
Main.cpp:22:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<Node*, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(int i=0; i<e.size(); i++)
      |                ~^~~~~~~~~
Main.cpp: In function 'int main(int, char**)':
Main.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d%lld", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   scanf("%d%d%lld", &a, &b, &l);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...