#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> con[30005];
int parent[30005];
int depth[30005];
int head[30005];
int heavy[30005];
int siz[30005];
int pos[30005], curpos;
int tin[30005];
int tout[30005];
int timer;
int aint[120100][21][21];
void upd(int nod, int st, int dr, int poz, int newv, int x, int y)
{
if(st==dr)
{
aint[nod][x][y]+=newv;
return;
}
int mij=(st+dr)/2;
if(poz<=mij) upd(nod*2,st,mij,poz,newv,x,y);
else upd(nod*2+1,mij+1,dr,poz,newv,x,y);
aint[nod][x][y] = aint[nod*2][x][y] + aint[nod*2+1][x][y];
}
int qry(int nod, int st, int dr, int le, int ri, int x, int y)
{
if(le>ri)
return 0;
if(le==st && dr==ri)
return aint[nod][x][y];
int mij=(st+dr)/2;
return qry(nod*2,st,mij,le,min(mij,ri),x,y)+
qry(nod*2+1,mij+1,dr,max(mij+1,le),ri,x,y);
}
bool isanc(int x, int y)
{
if(tin[x]<=tin[y] && tout[x]>=tout[y])
return 1;
return 0;
}
void dfs_init(int nod)
{
heavy[nod]=-1;
siz[nod]=1;
tin[nod]=++timer;
int maxc=0;
for(auto adj:con[nod])
{
if(adj!=parent[nod])
{
depth[adj]=depth[nod]+1;
parent[adj]=nod;
dfs_init(adj);
siz[nod]+=siz[adj];
if(siz[adj]>maxc)
maxc=siz[adj], heavy[nod]=adj;
}
}
tout[nod]=++timer;
}
void decompose(int nod, int chead)
{
pos[nod]=++curpos;
head[nod]=chead;
if(heavy[nod]!=-1)
decompose(heavy[nod], chead);
for(auto adj:con[nod])
if(adj!=parent[nod] && adj!=heavy[nod])
decompose(adj, adj);
}
int qry_hld(int a, int b, int x, int y)
{
int rez=0;
for(;head[a]!=head[b];b=parent[head[b]])
{
if(depth[head[a]]>depth[head[b]])
swap(a,b);
rez += qry(1,1,n,pos[head[b]],pos[b],x,y);
}
if(pos[b]>pos[a])
swap(a,b);
rez += qry(1,1,n,pos[b],pos[a],x,y);
return rez;
}
void init_hld()
{
dfs_init(1);
decompose(1,1);
}
void doupd(int x, int y, int newv)
{
vector<int> v;
vector<int> v2;
while(!isanc(x,y))
{
v.push_back(x);
x = parent[x];
}
v.push_back(x);
while(y!=x)
{
v2.push_back(y);
y = parent[y];
}
int lun = (int)v.size() + (int)v2.size();
int cnt=0;
for(int i=0;i<v.size();i++)
{
upd(1,1,n,pos[v[i]],newv,lun,cnt);
cnt++;
}
for(int i=(int)v2.size()-1;i>=0;i--)
{
upd(1,1,n,pos[v2[i]],newv,lun,cnt);
cnt++;
}
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
int a,b;
for(int i=1;i<n;i++)
{
cin>>a>>b;
con[a].push_back(b);
con[b].push_back(a);
}
init_hld();
int cntk,cntq,tip,t1,t2;
cin>>cntk;
for(int i=0;i<cntk;i++)
{
cin>>a>>b;
doupd(a,b,1);
}
cin>>cntq;
for(int i=0;i<cntq;i++)
{
cin>>tip;
if(tip==1)
{
cin>>a>>b;
doupd(a,b,1);
}
else if(tip==2)
{
cin>>a>>b;
doupd(a,b,-1);
}
else
{
cin>>a>>b>>t1>>t2;
t1--;
int rez=0;
for(int d=1;d<=20;d++)
{
for(int r=0;r<d;r++)
{
int cnt = qry_hld(a,b,d,r);
rez += cnt * (max(0,(t2-r+d)/d) - max(0,(t1-r+d)/d));
}
}
cout<<rez<<"\n";
}
}
return 0;
}
Compilation message
traffickers.cpp: In function 'void doupd(int, int, int)':
traffickers.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3416 KB |
Output is correct |
| 2 |
Correct |
11 ms |
5464 KB |
Output is correct |
| 3 |
Correct |
13 ms |
5588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
155 ms |
59996 KB |
Output isn't correct |
| 2 |
Incorrect |
192 ms |
59736 KB |
Output isn't correct |
| 3 |
Incorrect |
124 ms |
60456 KB |
Output isn't correct |
| 4 |
Incorrect |
156 ms |
60248 KB |
Output isn't correct |
| 5 |
Incorrect |
192 ms |
60240 KB |
Output isn't correct |
| 6 |
Incorrect |
167 ms |
59996 KB |
Output isn't correct |
| 7 |
Incorrect |
164 ms |
59996 KB |
Output isn't correct |
| 8 |
Incorrect |
131 ms |
60244 KB |
Output isn't correct |
| 9 |
Incorrect |
163 ms |
60388 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1758 ms |
121612 KB |
Output isn't correct |
| 2 |
Incorrect |
1465 ms |
122680 KB |
Output isn't correct |
| 3 |
Incorrect |
1497 ms |
122172 KB |
Output isn't correct |
| 4 |
Incorrect |
2434 ms |
121508 KB |
Output isn't correct |
| 5 |
Incorrect |
3020 ms |
120844 KB |
Output isn't correct |
| 6 |
Incorrect |
1453 ms |
122452 KB |
Output isn't correct |
| 7 |
Incorrect |
1640 ms |
122896 KB |
Output isn't correct |
| 8 |
Incorrect |
1685 ms |
122556 KB |
Output isn't correct |
