oj.uz

Submission #493742

# Submission time Handle Problem Language Result Execution time Memory
493742 2021-12-12T18:30:31 Z ivan_tudor Traffickers (RMI18_traffickers) C++17
75 / 100
 3500 ms 215932 KB 
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

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;
  }
};
inline 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];
inline void update(register int nod, register int l, register int r, register int poz, register int mod, register int rst, register int val){
  if(l > poz || r < poz)
    return;
  if(l == r){
    update_SegTree(aint[nod], mod, rst, val);
    return;
  }
  int mid = (l + r)/2;
  if(poz <= mid)
    update(2*nod, l, mid, poz, mod, rst, val);
  else
    update(2*nod + 1, mid + 1, r, poz, mod, rst, val);
  update_SegTree(aint[nod], mod, rst, val);
}
inline long long query(register int nod, register int l, register int r, register int ql, register int qr, register 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 = 0 , rgt = 0;
  if(ql <= mid)
    lft = query(2*nod, l, mid, ql, qr, t);
  if(qr > mid)
    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;
}

Compilation message

traffickers.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
traffickers.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
traffickers.cpp:23:33: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   23 | inline void update(register int nod, register int l, register int r, register int poz, register int mod, register int rst, register int val){
      |                                 ^~~
traffickers.cpp:23:51: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   23 | inline void update(register int nod, register int l, register int r, register int poz, register int mod, register int rst, register int val){
      |                                                   ^
traffickers.cpp:23:67: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   23 | inline void update(register int nod, register int l, register int r, register int poz, register int mod, register int rst, register int val){
      |                                                                   ^
traffickers.cpp:23:83: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   23 | inline void update(register int nod, register int l, register int r, register int poz, register int mod, register int rst, register int val){
      |                                                                                   ^~~
traffickers.cpp:23:101: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   23 | inline void update(register int nod, register int l, register int r, register int poz, register int mod, register int rst, register int val){
      |                                                                                                     ^~~
traffickers.cpp:23:119: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   23 | inline void update(register int nod, register int l, register int r, register int poz, register int mod, register int rst, register int val){
      |                                                                                                                       ^~~
traffickers.cpp:23:137: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   23 | inline void update(register int nod, register int l, register int r, register int poz, register int mod, register int rst, register int val){
      |                                                                                                                                         ^~~
traffickers.cpp:37:37: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   37 | inline long long query(register int nod, register int l, register int r, register int ql, register int qr, register int t){
      |                                     ^~~
traffickers.cpp:37:55: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   37 | inline long long query(register int nod, register int l, register int r, register int ql, register int qr, register int t){
      |                                                       ^
traffickers.cpp:37:71: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   37 | inline long long query(register int nod, register int l, register int r, register int ql, register int qr, register int t){
      |                                                                       ^
traffickers.cpp:37:87: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   37 | inline long long query(register int nod, register int l, register int r, register int ql, register int qr, register int t){
      |                                                                                       ^~
traffickers.cpp:37:104: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   37 | inline long long query(register int nod, register int l, register int r, register int ql, register int qr, register int t){
      |                                                                                                        ^~
traffickers.cpp:37:121: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   37 | inline long long query(register int nod, register int l, register int r, register int ql, register int qr, register int t){
      |                                                                                                                         ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 208396 KB Output is correct
2 Correct 81 ms 208696 KB Output is correct
3 Correct 86 ms 208560 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1786 ms 210696 KB Output is correct
2 Correct 1294 ms 210472 KB Output is correct
3 Correct 675 ms 210968 KB Output is correct
4 Correct 1865 ms 210980 KB Output is correct
5 Correct 1476 ms 210912 KB Output is correct
6 Correct 1780 ms 210752 KB Output is correct
7 Correct 1894 ms 210600 KB Output is correct
8 Correct 635 ms 210824 KB Output is correct
9 Correct 156 ms 210736 KB Output is correct

Subtask #3
15.0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3605 ms 214632 KB Time limit exceeded
2 Execution timed out 3586 ms 215560 KB Time limit exceeded
3 Execution timed out 3601 ms 215012 KB Time limit exceeded
4 Execution timed out 3591 ms 214436 KB Time limit exceeded
5 Correct 3385 ms 214564 KB Output is correct
6 Execution timed out 3538 ms 215484 KB Time limit exceeded
7 Correct 840 ms 215932 KB Output is correct
8 Correct 849 ms 215640 KB Output is correct