/*
"care a facut teste cu Lattice reduction attack e ciudat"
"linistiti va putin"
- 2023 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
struct Node
{
int maxval;
int maxvalpoz;
int minval;
int minvalpoz;
int lazy;
};
int dp[1000005]; /// dp[u] = costul sa il fortam pe soricel sa se intoarca la u
vector<int> nodes[1000005];
int depth[1000005];
int p[1000005];
int nxt[1000005];
int variante[1000005];
int lim[1000005];
int leftie[1000005];
int rightie[1000005];
int n,t,m,cnt;
const int INF=1e9;
///AINT
class AINT
{
private:
Node aint[4000005];
public:
void prop(int val)
{
if (aint[val].lazy==0)
return;
aint[val].maxval+=aint[val].lazy;
aint[val].minval+=aint[val].lazy;
if (val*2+1<=4*n)
{
aint[val*2].lazy+=aint[val].lazy;
aint[val*2+1].lazy+=aint[val].lazy;
}
aint[val].lazy=0;
}
void build(int l, int r, int val, int num)
{
if (l==r)
{
if (num==1)
{
aint[val]= {variante[l],l,variante[l],l,0};
}
else
{
aint[val]= {lim[l],l,lim[l],l,0};
}
return;
}
int mid;
mid=(l+r)/2;
build(l,mid,val*2,num);
build(mid+1,r,val*2+1,num);
aint[val]=combine(aint[val*2],aint[val*2+1]);
}
void lazy_update(int l, int r, int val, int qa, int qb, int x)
{
prop(val);
if (qa<=l && r<=qb)
{
aint[val].lazy+=x;
return;
}
int mid;
mid=(l+r)/2;
if (qa<=mid)
lazy_update(l,mid,val*2,qa,qb,x);
if (qb>mid)
lazy_update(mid+1,r,val*2+1,qa,qb,x);
prop(val*2);
prop(val*2+1);
aint[val]=combine(aint[val*2],aint[val*2+1]);
}
Node query(int l, int r, int val, int qa, int qb)
{
prop(val);
if (qa<=l && r<=qb)
{
return aint[val];
}
Node ans;
int mid;
ans= {-INF,0,INF,0,0};
mid=(l+r)/2;
if (qa<=mid)
ans=combine(ans,query(l,mid,val*2,qa,qb));
if (qb>mid)
ans=combine(ans,query(mid+1,r,val*2+1,qa,qb));
return ans;
}
void disable(int l, int r, int val, int poz)
{
prop(val);
if (l==r)
{
aint[val]= {-INF,0,INF,0,0};
return;
}
int mid;
mid=(l+r)/2;
if (poz<=mid)
disable(l,mid,val*2,poz);
else
disable(mid+1,r,val*2+1,poz);
prop(val*2);
prop(val*2+1);
aint[val]=combine(aint[val*2],aint[val*2+1]);
}
Node combine(Node a, Node b)
{
Node c;
if (a.minval!=b.minval)
{
if (a.minval<b.minval)
{
c.minval=a.minval;
c.minvalpoz=a.minvalpoz;
}
else
{
c.minval=b.minval;
c.minvalpoz=b.minvalpoz;
}
}
else
{
if (a.minvalpoz<b.minvalpoz)
{
c.minval=a.minval;
c.minvalpoz=a.minvalpoz;
}
else
{
c.minval=b.minval;
c.minvalpoz=b.minvalpoz;
}
}
if (a.maxval!=b.maxval)
{
if (a.maxval>b.maxval)
{
c.maxval=a.maxval;
c.maxvalpoz=a.maxvalpoz;
}
else
{
c.maxval=b.maxval;
c.maxvalpoz=b.maxvalpoz;
}
}
else
{
if (a.maxvalpoz<b.maxvalpoz)
{
c.maxval=a.maxval;
c.maxvalpoz=a.maxvalpoz;
}
else
{
c.maxval=b.maxval;
c.maxvalpoz=b.maxvalpoz;
}
}
c.lazy=0;
return c;
}
} aint1, aint2;
void calc(int node, int parent)
{
int mx1,mx2;
mx1=0;
mx2=0;
for (auto x : nodes[node])
{
if (x!=parent)
calc(x,node);
if (dp[x]>mx1)
{
mx2=mx1;
mx1=dp[x];
}
else if (dp[x]>mx2)
{
mx2=dp[x];
}
}
dp[node]=1+mx2+(nodes[node].size()-1-2)+1;
}
void dfs(int node, int parent)
{
for (auto x : nodes[node])
{
if (x!=parent)
{
p[x]=node;
depth[x]=depth[node]+1;
dfs(x,node);
}
}
}
void build_path(int l, int r)
{
int cr,cl,start,en,sofar,pending,len,last,i;
cr=r;
cl=l;
len=0;
while (depth[r]>depth[l])
{
nxt[p[r]]=r;
r=p[r];
len++;
}
while (depth[l]>depth[r])
{
nxt[l]=p[l];
l=p[l];
len++;
}
while (r!=l)
{
nxt[p[r]]=r;
nxt[l]=p[l];
l=p[l];
r=p[r];
len+=2;
}
r=cr;
l=nxt[cl];
cnt=0;
sofar=0;
last=cl;
while (l!=r)
{
start=cnt;
en=start;
pending=0;
for (auto x : nodes[l])
{
if (x!=nxt[l] && x!=last)
{
pending++;
en++;
}
}
sofar+=pending;
for (auto x : nodes[l])
{
if (x!=nxt[l] && x!=last)
{
calc(x,l);
variante[++cnt]=dp[x]+sofar;
lim[cnt]=len;
leftie[cnt]=start;
rightie[cnt]=en;
}
}
last=l;
l=nxt[l];
len--;
}
start=cnt;
en=start;
pending=0;
for (auto x : nodes[l])
{
if (x!=nxt[l] && x!=last)
{
pending++;
en++;
}
}
sofar+=pending;
for (auto x : nodes[l])
{
if (x!=nxt[l] && x!=last)
{
calc(x,l);
variante[++cnt]=dp[x]+sofar;
lim[cnt]=len;
leftie[cnt]=start;
rightie[cnt]=en;
}
}
}
signed main()
{
//ifstream fin("secvp.in");
//ofstream fout("secvp.out");
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int u,v,i,lbound,rbound;
Node ans,ans2;
bool ok;
cin >> n >> t >> m;
for (i=1; i<=n-1; i++)
{
cin >> u >> v;
nodes[u].push_back(v);
nodes[v].push_back(u);
}
depth[1]=1;
dfs(1,-1);
build_path(t,m);
aint1.build(0,cnt,1,1);
aint2.build(0,cnt,1,2);
ok=true;
while (ok)
{
ans=aint1.query(0,cnt,1,0,cnt);
lbound=leftie[ans.maxvalpoz];
rbound=rightie[ans.maxvalpoz];
if (rbound==0 && ans.maxvalpoz==0)
assert(0);
ans2=aint2.query(0,cnt,1,1,rbound);
if (ans2.minval==0)
{
cout << ans.maxval;
return 0;
}
else
{
aint1.disable(0,cnt,1,ans.maxvalpoz);
aint1.lazy_update(0,cnt,1,0,lbound,1);
aint2.lazy_update(0,cnt,1,1,rbound,-1);
}
}
}
Compilation message
mousetrap.cpp: In function 'void build_path(long long int, long long int)':
mousetrap.cpp:227:47: warning: unused variable 'i' [-Wunused-variable]
227 | int cr,cl,start,en,sofar,pending,len,last,i;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
48220 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
202 ms |
86608 KB |
Output is correct |
| 2 |
Correct |
173 ms |
80208 KB |
Output is correct |
| 3 |
Correct |
641 ms |
84780 KB |
Output is correct |
| 4 |
Correct |
267 ms |
54356 KB |
Output is correct |
| 5 |
Correct |
578 ms |
84800 KB |
Output is correct |
| 6 |
Correct |
623 ms |
84816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
48220 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
48220 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
