답안 #382093

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
382093 2021-03-26T11:36:12 Z mohamedsobhi777 Traffickers (RMI18_traffickers) C++14
15 / 100
3500 ms 11884 KB
#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 = 3e4 + 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;
}
// add(i , j , d) means +d at t = x * i + j

vii tms[22][22];

void add(int u, int v, int z, int d)
{
       tms[u][v].pb({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 calc(int u, int v, int t1, int t2)
{
       int ret = 0;
       for (int i = 1; i <= 20; ++i)
       {
              for (int j = 0; j < i; ++j)
              {
                     for (auto node : tms[i][j])
                     {
                            if (!belong(u, v, node.f))
                                   continue;
                            int 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 += add * node.s;
                     }
              }
       }
       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
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1132 KB Output is correct
2 Correct 546 ms 1388 KB Output is correct
3 Correct 614 ms 1388 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3568 ms 3196 KB Time limit exceeded
2 Execution timed out 3535 ms 3392 KB Time limit exceeded
3 Execution timed out 3537 ms 3500 KB Time limit exceeded
4 Execution timed out 3575 ms 3216 KB Time limit exceeded
5 Execution timed out 3590 ms 3180 KB Time limit exceeded
6 Execution timed out 3589 ms 3180 KB Time limit exceeded
7 Execution timed out 3586 ms 3200 KB Time limit exceeded
8 Execution timed out 3597 ms 3180 KB Time limit exceeded
9 Execution timed out 3581 ms 3436 KB Time limit exceeded
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3593 ms 11116 KB Time limit exceeded
2 Execution timed out 3575 ms 11756 KB Time limit exceeded
3 Execution timed out 3595 ms 11500 KB Time limit exceeded
4 Execution timed out 3599 ms 10860 KB Time limit exceeded
5 Execution timed out 3585 ms 10860 KB Time limit exceeded
6 Execution timed out 3592 ms 11628 KB Time limit exceeded
7 Execution timed out 3600 ms 11884 KB Time limit exceeded
8 Execution timed out 3596 ms 11516 KB Time limit exceeded