Submission #476603

#TimeUsernameProblemLanguageResultExecution timeMemory
476603stefantagaTraffickers (RMI18_traffickers)C++14
15 / 100
3598 ms207340 KiB
#include <bits/stdc++.h> using namespace std; class SegTree { int *arb[21][21]; public: void Initialize(int lung) { int i,j; for (i=1; i<=20; i++) { for (j=0; j<i; j++) { arb[i][j]= new int [(4*lung+1)]; for (int t=0; t<=4*lung; t++) { arb[i][j][t]=0; } } } } void update(int st,int dr,int nod,int poz,int val,int i,int j) { if (st>dr) { return; } if (st==dr) { arb[i][j][nod]+=val; return; } int mij=(st+dr)/2; if (poz<=mij) { update(st,mij,2*nod,poz,val,i,j); } else { update(mij+1,dr,2*nod+1,poz,val,i,j); } arb[i][j][nod]=arb[i][j][2*nod]+arb[i][j][2*nod+1]; } int query(int st,int dr,int nod,int ua,int ub,int i,int j) { if (ua<=st&&dr<=ub) { return arb[i][j][nod]; } int mij=(st+dr)/2,sum=0; if (ua<=mij) { sum=sum+query(st,mij,2*nod,ua,ub,i,j); } if (mij<ub) { sum=sum+query(mij+1,dr,2*nod+1,ua,ub,i,j); } return sum; } }*ceam; int tata[100005],niv[100005],mar[100005],poz[100005],lung[100005],id[100005],prim[100005],max_fiu[100005]; vector <int> v[100005]; void dfs(int x,int t) { tata[x]=t; mar[x]=1; niv[x]=niv[t]+1; for (int i=0; i<v[x].size(); i++) { int nod=v[x][i]; if (v[x][i]!=t) { dfs(v[x][i],x); mar[x]+=mar[nod]; if (mar[nod]>mar[max_fiu[x]]) { max_fiu[x]=nod; } } } } int q; void construieste(int x,int t) { ++lung[q]; poz[x]=lung[q]; if (lung[q]==1) { prim[q]=x; } id[x]=q; if (mar[x]==1) { return; } construieste(max_fiu[x],x); for (int i=0; i<v[x].size(); i++) { if (v[x][i]!=tata[x]&&v[x][i]!=max_fiu[x]) { q++; construieste(v[x][i],x); } } } int rmq[100005][20],lg; int lca(int x,int y) { if (niv[x]<niv[y]) { return lca(y,x); } int dif=niv[x]-niv[y]; for (int i=0; i<=lg; i++) { if ((dif&(1<<i))) { x=rmq[x][i]; } } if (x!=y) { for (int i=lg; i>=0; i--) { if (rmq[x][i]!=rmq[y][i]) { x=rmq[x][i]; y=rmq[y][i]; } } x=rmq[x][0]; } return x; } void updatetrafic(int x,int y,int valoare) { int salut,lungime,nr; salut=lca(x,y); lungime=niv[x]+niv[y]-2*niv[salut]+1; nr=0; while (x!=tata[salut]) { ceam[id[x]].update(1,lung[id[x]],1,poz[x],valoare,lungime,nr); nr++; x=tata[x]; } nr=lungime-1; x=y; while (x!=salut) { ceam[id[x]].update(1,lung[id[x]],1,poz[x],valoare,lungime,nr); nr--; x=tata[x]; } } int min1(int x,int y) { if (x>y) { return y; } return x; } int max1(int x,int y) { if (x<y) { return y; } return x; } int catesunt(int x,int y,int i,int j) { if (id[x]==id[y]) { int st=min1(poz[x],poz[y]); int dr=max1(poz[x],poz[y]); return ceam[id[x]].query(1,lung[id[x]],1,st,dr,i,j); } if (niv[prim[id[x]]]>niv[prim[id[y]]]) { swap(x,y); } return catesunt(y,prim[id[y]],i,j)+catesunt(tata[prim[id[y]]],x,i,j); } int rasp(int x,int y,int timp) { int i,j; int suma=0,numar=0; if (timp<0) { return 0; } for (i=1; i<=20; i++) { for (j=0; j<i; j++) { if (timp<j) { numar=0; } else { numar=(timp-j)/i+1; } suma=suma+(1LL*catesunt(x,y,i,j)*numar); } } return suma; } int n,x,i,j,y,queryuri,tip,t1,t2; int main() { ios_base :: sync_with_stdio(false); cin.tie(0); #ifdef HOME ifstream cin("date.in"); ofstream cout("date.out"); #endif // HOME cin>>n; for (i=1; i<n; i++) { cin>>x>>y; v[x].push_back(y); v[y].push_back(x); } q=1; dfs(1,0); for (i=1; i<=n; i++) { rmq[i][0]=tata[i]; } lg=log2(n); for (i=1; i<=lg; i++) { for (j=1; j<=n; j++) { rmq[j][i]=rmq[rmq[j][i-1]][i-1]; } } construieste(1,0); ceam= new SegTree [(q+1)]; for (i=1; i<=q; i++) { ceam[i].Initialize(lung[i]); } int traficanti; cin>>traficanti; for (i=1; i<=traficanti; i++) { cin>>x>>y; updatetrafic(x,y,1); } cin>>queryuri; for (int t=1; t<=queryuri; t++) { cin>>tip; if (tip==1) { cin>>x>>y; updatetrafic(x,y,1); } else if (tip==2) { cin>>x>>y; updatetrafic(x,y,-1); } else { cin>>x>>y>>t1>>t2; cout<<rasp(x,y,t2)-rasp(x,y,t1-1)<<'\n'; } } return 0; }

Compilation message (stderr)

traffickers.cpp: In function 'void dfs(int, int)':
traffickers.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i=0; i<v[x].size(); i++)
      |                   ~^~~~~~~~~~~~
traffickers.cpp: In function 'void construieste(int, int)':
traffickers.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (int i=0; i<v[x].size(); i++)
      |                   ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...