oj.uz

Submission #478222

# Submission time Handle Problem Language Result Execution time Memory
478222 2021-10-06T14:37:47 Z Alexandruabcde Traffickers (RMI18_traffickers) C++14
100 / 100
 1157 ms 108872 KB 
#include <bits/stdc++.h>
#define ub(x) (x&(-x))

using namespace std;

constexpr int NMAX = 5e4 + 5;
constexpr int DMAX = 21;
typedef long long LL;

vector <int> G[NMAX];

int N;

vector <int> E;
int Lvl[NMAX];
int RMQ[20][2*NMAX];
int lg[2*NMAX];
int first[NMAX], last[NMAX];
int T[NMAX];
int D = 20;

LL aib[DMAX][DMAX][2*NMAX];

void Update (int ind, int x, int y, LL val) {
    for (int i = x; i <= ind; i += ub(i))
        for (int j = y; j < E.size(); j += ub(j))
            aib[ind][i][j] += val;
}

LL Query (int ind, int x, int y) {
    LL S = 0;

    for (int i = x; i > 0; i -= ub(i))
        for (int j = y; j > 0; j -= ub(j))
            S += aib[ind][i][j];

    return S;
}

void Do_Graph () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 1; i < N; ++ i ) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void Euler (int node, int dad = 0) {
    E.push_back(node);
    Lvl[node] = Lvl[dad] + 1;
    T[node] = dad;
    for (auto it : G[node])
        if (it != dad) {
            Euler(it, node);
            E.push_back(node);
        }
}

int Minimum (int x, int y) {
    if (Lvl[E[x]] < Lvl[E[y]]) return x;

    return y;
}

void Rmq () {
    lg[1] = 0;
    for (int i = 2; i <= E.size(); ++ i )
        lg[i] = lg[i/2] + 1;
    for (int i = 1; i < E.size(); ++ i )
        RMQ[0][i] = i;

    for (int i = 1; (1<<i) < E.size(); ++ i ) {
        for (int j = 1; j + (1<<i) - 1 < E.size(); ++ j ) {
            RMQ[i][j] = Minimum(RMQ[i-1][j], RMQ[i-1][j+(1<<(i-1))]);
        }
    }
}

int LCA (int x, int y) {
    if (first[x] > first[y]) swap(x, y);

    int k = lg[first[y] - first[x]+1];

    return E[Minimum(RMQ[k][first[x]], RMQ[k][first[y] - (1<<k) + 1])];
}

void Do_LCA () {
    E.push_back(-1);
    Lvl[0] = -1;
    Euler(1);
    Rmq();

    for (int i = 1; i < E.size(); ++ i ) {
        if (!first[E[i]]) first[E[i]] = i;
        last[E[i]] = i;
    }
}

void Traficant (int x, int y, int val) {
    int cx = x, cy = y;
    vector <int> X, Y;

    while (cx != cy) {
        if (Lvl[cx] < Lvl[cy]) {
            Y.push_back(cy);
            cy = T[cy];
        }
        else {
            X.push_back(cx);
            cx = T[cx];
        }
    }
    X.push_back(cx);

    int d = X.size() + Y.size();

    for (int i = 0; i < X.size(); ++ i ) {
        Update(d, i+1, first[X[i]], 1LL * val);
        Update(d, i+1, last[X[i]]+1, 1LL * (-val));
    }
    for (int i = Y.size() - 1; i >= 0; -- i ) {
        Update(d, X.size() + (Y.size() - i), first[Y[i]], 1LL * val);
        Update(d, X.size() + (Y.size() - i), last[Y[i]]+1, 1LL * (-val));
    }
}

LL Prefix (int node, int Timp) {
    LL sol = 0;
    for (int i = 1; i <= D; ++ i ) {
        int aux = Query(i, i, first[node]);

        sol = sol + 1LL * (Timp / i) * aux;
        aux = Timp - (Timp/i)*i;
        sol = sol + 1LL * Query(i, aux, first[node]);
    }
    return sol;
}

LL Calculez (int x, int y, int Timp) {
    int z = LCA(x, y);

    return (Prefix(x, Timp) - Prefix(T[z], Timp)) + (Prefix(y, Timp) - Prefix(T[z], Timp)) - (Prefix(z, Timp) - Prefix(T[z], Timp));
}

void Solve () {
    int Q;

    cin >> Q;

    for (; Q; -- Q ) {
        int tip, x, y;

        cin >> tip >> x >> y;

        if (tip == 1) {
            Traficant(x, y, 1);
        }
        else if (tip == 2) {
            Traficant(x, y, -1);
        }
        else {
            int T1, T2;
            cin >> T1 >> T2;

            ++T1, ++T2;
            cout << Calculez(x, y, T2) - Calculez(x, y, T1-1) << '\n';
        }
    }
}

int main()
{
    Do_Graph();
    Do_LCA();

    int K;
    cin >> K;
    for (int i = 1; i <= K; ++ i ) {
        int x, y;
        cin >> x >> y;
        Traficant(x, y, 1);
    }

    Solve();

    return 0;
}

Compilation message

traffickers.cpp: In function 'void Update(int, int, int, LL)':
traffickers.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for (int j = y; j < E.size(); j += ub(j))
      |                         ~~^~~~~~~~~~
traffickers.cpp: In function 'void Rmq()':
traffickers.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 2; i <= E.size(); ++ i )
      |                     ~~^~~~~~~~~~~
traffickers.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i = 1; i < E.size(); ++ i )
      |                     ~~^~~~~~~~~~
traffickers.cpp:78:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 1; (1<<i) < E.size(); ++ i ) {
      |                     ~~~~~~~^~~~~~~~~~
traffickers.cpp:79:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int j = 1; j + (1<<i) - 1 < E.size(); ++ j ) {
      |                         ~~~~~~~~~~~~~~~^~~~~~~~~~
traffickers.cpp: In function 'void Do_LCA()':
traffickers.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (int i = 1; i < E.size(); ++ i ) {
      |                     ~~^~~~~~~~~~
traffickers.cpp: In function 'void Traficant(int, int, int)':
traffickers.cpp:123:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for (int i = 0; i < X.size(); ++ i ) {
      |                     ~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 7 ms 6220 KB Output is correct
3 Correct 7 ms 6092 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 37496 KB Output is correct
2 Correct 108 ms 33972 KB Output is correct
3 Correct 92 ms 36044 KB Output is correct
4 Correct 96 ms 37708 KB Output is correct
5 Correct 115 ms 37464 KB Output is correct
6 Correct 117 ms 37580 KB Output is correct
7 Correct 109 ms 37004 KB Output is correct
8 Correct 104 ms 37704 KB Output is correct
9 Correct 80 ms 37844 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1041 ms 108024 KB Output is correct
2 Correct 1016 ms 108764 KB Output is correct
3 Correct 1026 ms 108380 KB Output is correct
4 Correct 1006 ms 107460 KB Output is correct
5 Correct 1157 ms 107304 KB Output is correct
6 Correct 1010 ms 108736 KB Output is correct
7 Correct 866 ms 108872 KB Output is correct
8 Correct 916 ms 108456 KB Output is correct