Submission #382101

#	Time	Username	Problem	Language	Result	Execution time	Memory
382101		mohamedsobhi777	Traffickers (RMI18_traffickers)	C++14	100 / 100	3144 ms	214052 KiB

traffickers

#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound

using ll = long long;
using ld = long double;

const int N = 6e4 + 7;
const ll mod = 1e9 + 7;

int n, t;
vi adj[N];
int up[N][18];
int st[N], en[N];
int dep[N];

inline bool upper(int u, int v) { return st[u] <= st[v] && en[u] >= en[v]; }

int lca(int u, int v)
{
       if (upper(u, v))
              return u;
       if (upper(v, u))
              return v;
       for (int i = 17; ~i; --i)
       {
              if (!upper(up[u][i], v))
                     u = up[u][i];
       }
       return up[u][0];
}

void dfs(int x, int p)
{
       st[x] = ++t;
       up[x][0] = p;
       dep[x] = 1 + dep[p];
       for (int i = 1; i < 18; ++i)
       {
              up[x][i] = up[up[x][i - 1]][i - 1];
       }
       for (auto u : adj[x])
       {
              if (u != p)
              {
                     dfs(u, x);
              }
       }
       en[x] = ++t;
}

struct fenwick
{
       int bit[2 * N];
       fenwick()
       {
              memset(bit, 0, sizeof bit);
       }
       void add(int x, int v)
       {
              for (; x < N; x += x & -x)
                     bit[x] += v;
       }
       int upto(int x)
       {
              int ret = 0;
              for (; x; x -= x & -x)
                     ret += bit[x];
              return ret;
       }
       inline int get(int l, int r) { return upto(r) - upto(l - 1); }
} fs[21][21];

void add(int u, int v, int z, int d)
{
       fs[u][v].add(st[z], d);
       fs[u][v].add(en[z], -d);
}

int get(int a, int b)
{
       if (upper(b, a))
              swap(a, b);
       assert(upper(a, b));
       return dep[b] - dep[a];
}

int dist(int x, int y)
{
       int lc = lca(x, y);
       return get(x, lc) + get(y, lc);
}

bool belong(int x, int y, int z)
{
       return dist(x, y) == dist(x, z) + dist(z, y);
}

int inside(int a, int b, int c)
{
       if (a > b)
              return 0;
       return c >= a && c <= b;
}

int count_path(int u, int v, int i, int j)
{
       int ret = 0;
       int lc = lca(u, v);
       ret += fs[i][j].get(st[lc], st[u]);
       ret += fs[i][j].get(st[lc], st[v]);
       ret -= fs[i][j].get(st[lc], st[lc]);
       return ret;
}

ll calc(int u, int v, int t1, int t2)
{
       ll ret = 0;
       for (int i = 1; i <= 20; ++i)
       {
              for (int j = 0; j < i; ++j)
              {
                     ll count = count_path(u, v, i, j);
                     ll add = 0;
                     int tb1 = t1 / i;
                     int tb2 = t2 / i;
                     if (tb1 == tb2)
                     {
                            add += inside(t1 % i, t2 % i, j);
                     }
                     else
                     {
                            add += tb2 - tb1 - 1;
                            add += inside(t1 % i, i - 1, j);
                            add += inside(0, t2 % i, j);
                     }
                     ret += 1ll * add * count;
              }
       }
       return ret;
}

vi one_path(int u, int v)
{
       vi ret = {u};
       while (u != v)
       {
              u = up[u][0];
              ret.pb(u);
       }
       return ret;
}

vi get_path(int u, int v)
{

       int lc = lca(u, v);

       if (u == lc)
       {
              vi ret = one_path(v, u);
              reverse(all(ret));
              return ret;
       }
       else if (v == lc)
       {
              return one_path(u, v);
       }
       else
       {
              vi ret = one_path(u, lc);
              vi ret2 = one_path(v, lc);
              ret2.pop_back();
              reverse(all(ret2));
              ret.insert(ret.end(), all(ret2));
              return ret;
       }
       assert(0);
}

void Add(int u, int v, int d)
{
       vi g = get_path(u, v);
       for (int i = 0; i < sz(g); ++i)
              add(sz(g), i, g[i], d);
}

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
       // freopen("in.in", "r", stdin);
#endif
       cin >> n;
       for (int i = 0; i < n - 1; ++i)
       {
              int u, v;
              cin >> u >> v;
              adj[u].pb(v);
              adj[v].pb(u);
       }
       dfs(1, 1);
       int k;
       cin >> k;

       for (int i = 0; i < k; ++i)
       {
              int u, v;
              cin >> u >> v;
              Add(u, v, 1);
       }
       int q;
       cin >> q;
       for (int i = 0; i < q; ++i)
       {
              int ty, u, v;
              cin >> ty >> u >> v;
              if (ty == 1)
              {
                     Add(u, v, 1);
              }
              else if (ty == 2)
              {
                     Add(u, v, -1);
              }
              else
              {
                     int t1, t2;
                     cin >> t1 >> t2;
                     cout << calc(u, v, t1, t2) << "\n";
              }
       }
       return 0;
}

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