Submission #493739

#	Time	Username	Problem	Language	Result	Execution time	Memory
493739		ivan_tudor	Traffickers (RMI18_traffickers)	C++14	70 / 100	3605 ms	215972 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;
  }
};
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 = 16;
int sz[N];
int head[N], id[N];
int par[N], in[N];
int h[N];

int ord[2 * N];
int rmqord[LOGN ][2 * N];
int p2[2*N];
vector<int> gr[N];
void dfs_init (int nod, int dad, int &cord){
  sz[nod] = 1;
  par[nod] = dad;


  h[nod] = h[dad] + 1;
  ord[++cord] = nod;
  in[nod] = cord;
  for(auto x:gr[nod]){
    if(x == dad)
      continue;
    dfs_init(x, nod, cord);
    ord[++cord] = nod;
  }
}
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);
  }
}

int nrord;
void build_lca(){
  p2[1] = 0;
  for(int i = 2; i<2*N; i++)
    p2[i] = 1 + p2[i/2];
  for(int i =1 ; i<=nrord; i++){
    rmqord[0][i] = ord[i];
  }
  for(int log = 1; log < LOGN; log++){
    for(int i = 1; i<=nrord; i++){
      int n1 = rmqord[log - 1][i];
      int n2 = rmqord[log - 1][min(nrord, i + (1<<(log - 1)))];
      if(h[n1] < h[n2])
        rmqord[log][i] = n1;
      else
        rmqord[log][i] = n2;
    }
  }

}
int get_lca(int u, int v){
  u = in[u];
  v = in[v];
  if(u > v)
    swap(u, v);
  int len = v- u  + 1;
  int lg = p2[len];
  int n1 = rmqord[lg][u];
  int n2 = rmqord[lg][v - (1<<lg) + 1];
  if(h[n1] < h[n2])
    return n1;
  return n2;
}
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[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[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[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[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);
  nrord = cnt;
  build_lca();
  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