Submission #493722

#	Time	Username	Problem	Language	Result	Execution time	Memory
493722		ivan_tudor	Traffickers (RMI18_traffickers)	C++14	70 / 100	3591 ms	213668 KiB

traffickers

#include<bits/stdc++.h>
using namespace std;
const int N =30005;
const int DMAX = 21;
struct SegTree{
  int rest[DMAX][DMAX];
  SegTree(){
    for(int i = 0; i < DMAX; i++)
      for(int j = 0; j < DMAX; j++)
        rest[i][j] = 0;
  }
};
SegTree operator + (const SegTree &a,const SegTree &b){
  SegTree ans;
  for(int i = 0; i < DMAX; i++){
    for(int j = 0; j < DMAX; j++){
      ans.rest[i][j] = a.rest[i][j] + b.rest[i][j];
    }
  }
  return ans;
}
void update_SegTree(SegTree &a, int t, int poz, int val){
  for(int i = poz; i < t; i++){
    a.rest[t][i] += val;
  }
}
SegTree aint[4*N];
void update(int nod, int l, int r, int poz, int mod, int rst, int val){
  if(l > poz || r < poz)
    return;
  if(l == r){
    update_SegTree(aint[nod], mod, rst, val);
    return;
  }
  int mid = (l + r)/2;
  update(2*nod, l, mid, poz, mod, rst, val);
  update(2*nod + 1, mid + 1, r, poz, mod, rst, val);
  update_SegTree(aint[nod], mod, rst, val);
}
long long query(int nod, int l, int r, int ql, int qr, int t){
  if(r < ql || l > qr)
    return 0;
  if(ql <= l && r <= qr){
    long long rsp = 0;
    for(int i = 1; i < DMAX; i++){
      int cat = t/i;
      rsp += 1LL * cat * aint[nod].rest[i][i - 1];
      rsp += 1LL * aint[nod].rest[i][t%i];
    }
    return rsp;
  }
  int mid = (l + r)/2;
  long long lft = query(2*nod, l, mid, ql, qr, t);
  long long rgt = query(2*nod + 1, mid + 1, r, ql, qr, t);
  return lft + rgt;
}
/// segtree done


///hpd
const int LOGN = 15;
int sz[N];
int head[N], id[N];
int par[LOGN][N], in[N], out[N];
int h[N];
vector<int> gr[N];
void dfs_init (int nod, int dad, int &cnt){
  sz[nod] = 1;
  par[0][nod] = dad;
  for(int i = 1; i < LOGN; i++)
    par[i][nod] = par[i - 1][par[i - 1][nod]];
  in[nod] = ++cnt;
  h[nod] = h[dad] + 1;
  for(auto x:gr[nod]){
    if(x == dad)
      continue;
    dfs_init(x, nod, cnt);
  }
  out[nod] = cnt;
}
void dfs_buildhpd(int nod, int dad, int chead, int &idd){
  head[nod] = chead;
  id[nod] = ++idd;
  int mson = -1;
  for(auto x:gr[nod]){
    if(x == dad)
      continue;
    if(mson == -1 || sz[x] > sz[mson])
      mson = x;
  }
  if(mson == -1)
    return;
  dfs_buildhpd(mson, nod, chead, idd);
  for(auto x:gr[nod]){
    if(x == dad || x == mson)
      continue;
    dfs_buildhpd(x, nod, x, idd);
  }
}

bool is_ancestor(int dad, int son){
  if(in[dad] <= in[son] && out[son] <= out[dad])
    return true;
  return false;
}
int get_lca(int u, int v){
  if(h[u] > h[v])
    swap(u, v);
  if(is_ancestor(u, v))
    return u;
  for(int pas = LOGN - 1; pas >= 0; pas--){
    int most = par[pas][u];
    if(most != 0 && is_ancestor(most, v) == false)
      u = most;
  }
  if(is_ancestor(u, v))
    return u;
  return par[0][u];
}
int n;
void update_addway(int u, int v, int val){
  int lca = get_lca(u, v);

  int dst = h[u] - h[lca] +  h[v] - h[lca] + 1;
  int cnt = 0;
  while(u != lca){
    update(1, 1, n, id[u], dst, cnt, val);
    cnt++;
    u = par[0][u];
  }
  update(1, 1, n, id[lca], dst, cnt, val);

  cnt = dst - 1;
  while(v != lca){
    update(1, 1, n, id[v], dst, cnt, val);
    cnt--;
    v = par[0][v];
  }
}
long long query_chain(int u, int v, int t){
  int lca = get_lca(u, v);
  long long ans = 0;
  while(head[u] != head[lca]){
    ans += query(1, 1, n, id[head[u]], id[u], t);
    u = par[0][head[u]];
  }
  ans += query(1, 1, n, id[lca], id[u], t);

  while(head[v] != head[lca]){
    ans += query(1, 1, n, id[head[v]], id[v], t);
    v = par[0][head[v]];
  }
  if(id[lca] + 1 <= id[v])
    ans+=query(1, 1, n, id[lca] + 1, id[v], t);

  return ans;
}
int main()
{
 // freopen(".in","r",stdin);
  iostream::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin>>n;
  for(int i = 1; i<n; i++){
    int u, v;
    cin>>u>>v;
    gr[u].push_back(v);
    gr[v].push_back(u);
  }
  int cnt = 0;
  dfs_init(1, 0, cnt);
  cnt = 0;
  dfs_buildhpd(1, 0, 1, cnt);
  int k;
  cin>>k;
  for(int i = 1; i<=k; i++){
    int u, v;
    cin>>u>>v;
    update_addway(u, v, 1);
  }
  int q;
  cin>>q;
  for(int i = 1; i<=q; i++){
    int t;
    cin>>t;
    if(t == 1){
      int u, v;
      cin>>u>>v;
      update_addway(u, v, 1);
    }
    else if(t == 2){
      int u, v;
      cin>>u>>v;
      update_addway(u, v, -1);
    }
    else{
      int u, v, t1, t2;
      cin>>u>>v>>t1>>t2;
      long long rsp = query_chain(u, v, t2);
      if(t1 != 0)
        rsp -= query_chain(u, v, t1 - 1);
      cout<<rsp<<"\n";
    }
  }
  return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 10 / 40