Submission #522526

#TimeUsernameProblemLanguageResultExecution timeMemory
522526fcmalkcinPaths (RMI21_paths)C++17
0 / 100
24 ms35280 KiB
/*#pragma GCC optimize("Ofast") #pragma GCC optimization("unroll-loops, no-stack-protector") #pragma GCC target("avx,avx2,fma")*/ #include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define ff first #define ss second #define pb push_back #define endl "\n" #define For(i,a,b) for (ll i=a;i<=b;i++) mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); const ll maxn=2e5+100; const ll mod=998244353 ; const ll base=2e9+10000; /// you will be the best but now you just are trash /// goal 3/7 ll res[maxn]; vector<pll> adj[maxn]; pll st[4*maxn]; ll pos[maxn]; pll mer(pll a,pll b) { if (a.ff>=b.ff) return a; return b; } void update(ll id,ll left,ll right,ll x,ll diff) { if (x>right||x<left) return ; if (left==right) { st[id]=make_pair(diff,left); return ; } ll mid=(left+right)/2; update(id*2,left,mid,x,diff); update(id*2+1,mid+1,right,x,diff); st[id]=mer(st[id*2],st[id*2+1]); } pll get(ll id,ll left,ll right,ll x,ll y) { if (x>right||y<left) return make_pair(-1,0); if (x<=left&&y>=right) return st[id]; ll mid=(left+right)/2; return mer(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y)); } struct tk { pll st[4*maxn]; ll la[4*maxn]; tk() { for (int i=0; i<4*maxn; i++) { st[i]=make_pair(0,0); } memset(la,0,sizeof(st)); } pll mer(pll a,pll b) { if (a.ff>=b.ff) return a; return b; } void dosth(ll id,ll left,ll right) { st[id*2].ff+=la[id]; st[id*2+1].ff+=la[id]; la[id*2]+=la[id]; la[id*2+1]+=la[id]; la[id]=0; return ; } void update(ll id,ll left,ll right,ll x,ll y,ll diff) { if (x>right||y<left) return ; if (x<=left&&y>=right) { st[id].ff+=diff; la[id]+=diff; if (left==right) st[id].ss=left; return ; } dosth(id,left,right); ll mid=(left+right)/2; update(id*2,left,mid,x,y,diff); update(id*2+1,mid+1,right,x,y,diff); st[id]=mer(st[id*2],st[id*2+1]); } pll get(ll id,ll left,ll right,ll x,ll y) { if (x>right||y<left) return make_pair(-1,0); if (x<=left&&y>=right) return st[id]; dosth(id,left,right); ll mid=(left+right)/2; return mer(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y)); } } man; set<pll> st1; set<pll,greater<pll>> st2; ll ans=0; ll n, k; ll cnt=0; ll f[maxn]; ll l[maxn]; ll dep[maxn]; vector<ll> vt; ll val[maxn]; bool dd[maxn]; ll anc[maxn]; void add(ll u) { if (st1.size()<k) { st1.insert(make_pair(val[u],u)); ans+=val[u]; } else { if ((*st1.begin())<make_pair(val[u],u)) { auto p=(*st1.begin()); st1.erase(st1.begin()); st1.insert(make_pair(val[u],u)); ans+=val[u]; ans-=p.ff; st2.insert(p); } else { st2.insert(make_pair(val[u],u)); } } } void ers(ll u) { if (st1.count(make_pair(val[u],u))) { st1.erase(make_pair(val[u],u)); ans-=val[u]; if (st2.size()) { auto p=(*st2.begin()); st2.erase(p); st1.insert(p); ans+=p.ff; } } else { st2.erase(make_pair(val[u],u)); } } void change(ll u,ll val1) { if (val[u]) { ers(u); } update(1,1,n,f[u],val1); val[u]=val1; add(u); } void dfs(ll u,ll par) { anc[u]=par; cnt++; f[u]=cnt; pos[cnt]=u; for (auto p:adj[u]) { ll to=p.ff; ll w=p.ss; if (to==par) continue; dep[to]=dep[u]+w; dfs(to,u); } l[u]=cnt; if (l[u]==f[u]) { vt.pb(u); } } ll mxl[maxn]; void dfs1(ll u,ll par) { mxl[u]=u; for (auto p:adj[u]) { ll to=p.ff; ll w=p.ss; if (to==par) continue; dfs1(to,u); if (val[mxl[to]]>val[mxl[u]]) mxl[u]=mxl[to]; } } void dfs2(ll u,ll par,pll mxpre) { /* if (u==1) { for (auto to:st1) { cout <<to.ff<<" "<<to.ss<<" chk1"<<endl; } for (auto to:st2) { cout <<to.ff<<" "<<to.ss<<" chk2"<<endl; } }*/ res[u]=ans; for (auto p1:adj[u]) { ll to=p1.ff; ll w=p1.ss; if (to==par) continue; ll posnxt=mxl[to]; ll valnw=get(1,1,n,f[posnxt],l[posnxt]).ff; change(posnxt,valnw-w); auto p=mer(get(1,1,n,f[u],f[to]-1),get(1,1,n,l[to]+1,l[u])); if (p.ff>mxpre.ff) { p=make_pair(p.ff,pos[p.ss]); } else { p=mxpre; } /*if (to==1) { cout <<p.ff<<" "<<p.ss<<" "<<f[to]-1<<" "<<l[to]+1<<" "<<f[u]<<" "<<l[u]<<endl; }*/ change(p.ss,p.ff+w); dfs2(to,u,make_pair(p.ff+w,p.ss)); change(posnxt,valnw); change(p.ss,p.ff); } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen("popeala.inp", "r")) { freopen("popeala.inp", "r", stdin); freopen("popeala.out", "w", stdout); } cin>> n>> k; pll root=make_pair(0,1); for (int i=1; i<=n-1; i++) { ll x, y, w; cin>>x>> y>> w; adj[x].pb(make_pair(y,w)); adj[y].pb(make_pair(x,w)); root=max(root,make_pair((ll)adj[x].size(),x)); root=max(root,make_pair((ll)adj[y].size(),y)); } dd[0]=1; dfs(root.ss,0); // cout <<root.ss<<endl; k=min(k,(ll)vt.size()); for (auto to:vt) { man.update(1,1,n,f[to],l[to],dep[to]); // cout <<to<<" "<<dep[to]<<endl; } for (int i=1; i<=vt.size(); i++) { auto p=man.st[1]; assert(p.ff); ll u=pos[p.ss]; change(u,p.ff); ll nw=u; while (!dd[nw]) { dd[nw]=1; man.update(1,1,n,f[nw],l[nw],-(dep[nw]-dep[anc[nw]])); nw=anc[nw]; } } dfs1(root.ss,0); dfs2(root.ss,0,make_pair(-1,0)); for (int i=1;i<=n;i++) { cout <<res[i]<<endl; } }

Compilation message (stderr)

Main.cpp: In function 'void add(long long int)':
Main.cpp:129:19: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  129 |     if (st1.size()<k)
      |         ~~~~~~~~~~^~
Main.cpp: In function 'void dfs1(long long int, long long int)':
Main.cpp:208:12: warning: unused variable 'w' [-Wunused-variable]
  208 |         ll w=p.ss;
      |            ^
Main.cpp: In function 'int main()':
Main.cpp:289:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  289 |     for (int i=1; i<=vt.size(); i++)
      |                   ~^~~~~~~~~~~
Main.cpp:266:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  266 |         freopen("popeala.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:267:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  267 |         freopen("popeala.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/string.h:495,
                 from /usr/include/c++/10/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:48,
                 from Main.cpp:5:
In function 'void* memset(void*, int, size_t)',
    inlined from 'tk::tk()' at Main.cpp:68:15,
    inlined from 'void __static_initialization_and_destruction_0(int, int)' at Main.cpp:113:3,
    inlined from '(static initializers for Main.cpp)' at Main.cpp:309:1:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:71:33: warning: 'void* __builtin___memset_chk(void*, int, long unsigned int, long unsigned int)' forming offset [19209600, 25612799] is out of the bounds [0, 19209600] of object 'man' with type 'tk' [-Warray-bounds]
   71 |   return __builtin___memset_chk (__dest, __ch, __len, __bos0 (__dest));
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function '(static initializers for Main.cpp)':
Main.cpp:113:3: note: 'man' declared here
  113 | } man;
      |   ^~~
#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...