Submission #987580

#TimeUsernameProblemLanguageResultExecution timeMemory
987580ASN49KPaths (RMI21_paths)C++14
68 / 100
1054 ms22812 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define int long long struct poz_max { int maxx,poz; }; poz_max merge(const poz_max& a,const poz_max& b) { if(a.maxx>b.maxx || (a.maxx==b.maxx && a.poz>b.poz)) { return a; } return b; } struct Aint { int n; vector<poz_max>aint; void update(int poz,int val) { poz+=n; aint[poz].maxx=val; for(poz>>=1;poz>0;poz>>=1) { aint[poz]=merge(aint[poz<<1] , aint[poz<<1|1]); } } poz_max query(int l,int r) { l+=n; r+=n; poz_max rez={0,-1}; while(l<=r) { if(l&1)rez=merge(rez , aint[l++]); if(!(r&1))rez=merge(rez,aint[r--]); l>>=1; r>>=1; } return rez; } void init(int n) { this->n=n; aint=vector<poz_max>(2*n); for(int i=0;i<n;i++) { aint[i+n]={0,i}; } } Aint(){} Aint(int n) { init(n); } }; struct Edge { int to,dist; }; const int N=100'000; vector<Edge>g[N]; int tin[N],tout[N],rez[N]; Aint aint; multiset<int>mp; void change(int poz,int val1,int val2) { //assert(mp.count(-val1)); mp.erase(mp.find(-val1)); mp.insert(-val2); aint.update(poz,val2); } void dfs(int nod,int tt) { static int timp=-1; tin[nod]=++timp; for(auto &c:g[nod]) { if(c.to!=tt) { dfs(c.to,nod); auto it=aint.query(tin[c.to] , tout[c.to]); change(it.poz , it.maxx , it.maxx+c.dist); } } tout[nod]=timp; } int n,k; void reroot(int nod,int tt) { for(auto &c:g[nod]) { if(c.to!=tt) { auto sus=merge(aint.query(0,tin[c.to]-1) , aint.query(tout[c.to]+1 , n-1)); auto jos=aint.query(tin[c.to] , tout[c.to]); change(sus.poz , sus.maxx, sus.maxx+c.dist); change(jos.poz , jos.maxx, jos.maxx-c.dist); reroot(c.to,nod); change(sus.poz , sus.maxx+c.dist , sus.maxx); change(jos.poz , jos.maxx-c.dist , jos.maxx); } } int old_k=k; for(auto &c:mp) { rez[nod]-=c; if(--old_k == 0) { break; } } } main() { cin>>n>>k; aint.init(n); for(int i=1;i<n;i++) { int x,y,z; cin>>x>>y>>z; x--; y--; g[x].pb({y,z}); g[y].pb({x,z}); } for(int i=0;i<n;i++) { mp.insert(0); } dfs(0,0); reroot(0,0); for(int i=0;i<n;i++) { cout<<rez[i]<<'\n'; } return 0; }

Compilation message (stderr)

Main.cpp:121:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  121 | main()
      | ^~~~
#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...