| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 522536 |
2022-02-05T06:36:03 Z |
fcmalkcin |
Paths (RMI21_paths) |
C++17 |
|
1 ms |
588 KB |
/*#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=1e3+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("t.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.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));
}
if (n==1)
{
cout <<0;
return 0;
}
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
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:294:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
294 | 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("test.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("test.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:314: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 [105600, 140799] is out of the bounds [0, 105600] 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 time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
