Submission #1124534

#TimeUsernameProblemLanguageResultExecution timeMemory
1124534HNa_seawjingPetrol stations (CEOI24_stations)C++20
26 / 100
57 ms31300 KiB
#include <bits/stdc++.h> //code #define fl(i,x,y,z) for(int i=x;i<=y;i=i+z) #define fn(i,x,y,z) for(int i=x;i>=y;i=i-z) #define rep(i,x,y) for(int i=x;i<y;i=i+1) #define all(v) v.begin(),v.end() #define pb emplace_back #define tle cout<<"tle"<<endl #define edl cout<<"\n" #define el "\n" #define getbit(x,i) ((x>>i)&1) #define bitcnt __builtin_popcount //ham #define pii pair<int,int> #define fi first #define se second #define ll long long #define ld long double #define inf 0x3f3f3f3f //#define int long long template <typename T1, typename T2> bool minimize(T1 &a, T2 b) { if (a > b) { a = b; return true; } return false; } template <typename T1, typename T2> bool maximize(T1 &a, T2 b) { if (a < b) { a = b; return true; } return false; } using namespace std; const int maxn=1e6+5; int n,k; int a[maxn]; vector <pii> e[maxn]; ll res[maxn]; int sz[maxn]; int D=0,lmax=0; void inp() { cin>>n>>k; fl(i,1,n-1,1) { int u,v,l; cin>>u>>v>>l; e[u].pb(v,l); e[v].pb(u,l); lmax=max(lmax,l); } rep(i,0,n) D=max(D,(int)e[i].size()); } void sub12DFS(int u,int par) { sz[u]=1; for (auto it: e[u]) { int v=it.fi,l=it.se; if (v==par) continue; sub12DFS(v,u); sz[u]+=sz[v]; } } void sub1reDFS(int u,int par,int w) { for (auto it: e[u]) { int v=it.fi,l=it.se; if (v==par) continue; if (w-l<0) { res[u]+=sz[v]; sub1reDFS(v,u,k-l); } else sub1reDFS(v,u,w-l); } } void sub1() { rep(i,0,n) { sub12DFS(i,i); sub1reDFS(i,i,k); } rep(i,0,n) cout<< res[i]<<el; } void sub2() { int id; rep(i,0,n) if ((int)e[i].size()==1) id=i; sub12DFS(id,id); rep(i,0,n) { int x=n-sz[i],y=sz[i]-1; cout<< 1ll*(x/k)*y+ 1ll*(y/k)*x<<el; } } void sol() { if (n<=1000) sub1(); else if (D<=2 && lmax==1) sub2(); } signed main() { #define name "station" if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(NULL); inp(); sol(); return 0; } /* /\_/\ ( ._. ) / >V< \ */

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...