oj.uz

Submission #478191

# Submission time Handle Problem Language Result Execution time Memory
478191 2021-10-06T11:08:22 Z Alexandruabcde Traffickers (RMI18_traffickers) C++14
15 / 100
 1109 ms 61436 KB 
#include <bits/stdc++.h>
#define ub(x) (x&(-x))

using namespace std;

constexpr int NMAX = 5e4 + 5;
constexpr int DMAX = 21;

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;

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

void Update (int ind, int x, int y, int 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;
}

int Query (int ind, int x, int y) {
    int 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]], val);
        Update(d, i+1, last[X[i]]+1, -val);
    }
    for (int i = Y.size() - 1; i >= 0; -- i ) {
        Update(d, X.size() + (Y.size() - i), first[Y[i]], val);
        Update(d, X.size() + (Y.size() - i), last[Y[i]]+1, -val);
    }
}

int Prefix (int node, int Timp) {
    int 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;
}

int 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, int)':
traffickers.cpp:25:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (int j = y; j < E.size(); j += ub(j))
      |                         ~~^~~~~~~~~~
traffickers.cpp: In function 'void Rmq()':
traffickers.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 2; i <= E.size(); ++ i )
      |                     ~~^~~~~~~~~~~
traffickers.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 1; i < E.size(); ++ i )
      |                     ~~^~~~~~~~~~
traffickers.cpp:77:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 1; (1<<i) < E.size(); ++ i ) {
      |                     ~~~~~~~^~~~~~~~~~
traffickers.cpp:78:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for (int j = 1; j + (1<<i) - 1 < E.size(); ++ j ) {
      |                         ~~~~~~~~~~~~~~~^~~~~~~~~~
traffickers.cpp: In function 'void Do_LCA()':
traffickers.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int i = 1; i < E.size(); ++ i ) {
      |                     ~~^~~~~~~~~~
traffickers.cpp: In function 'void Traficant(int, int, int)':
traffickers.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for (int i = 0; i < X.size(); ++ i ) {
      |                     ~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2512 KB Output is correct
2 Correct 5 ms 4452 KB Output is correct
3 Correct 5 ms 4432 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 21248 KB Output isn't correct
2 Incorrect 72 ms 19428 KB Output isn't correct
3 Incorrect 68 ms 20688 KB Output isn't correct
4 Incorrect 78 ms 21440 KB Output isn't correct
5 Incorrect 85 ms 21216 KB Output isn't correct
6 Incorrect 81 ms 21384 KB Output isn't correct
7 Incorrect 74 ms 20940 KB Output isn't correct
8 Incorrect 80 ms 21484 KB Output isn't correct
9 Incorrect 62 ms 21564 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 898 ms 60656 KB Output isn't correct
2 Incorrect 905 ms 61384 KB Output isn't correct
3 Incorrect 815 ms 60892 KB Output isn't correct
4 Incorrect 906 ms 60228 KB Output isn't correct
5 Incorrect 1109 ms 59980 KB Output isn't correct
6 Incorrect 889 ms 61312 KB Output isn't correct
7 Incorrect 788 ms 61436 KB Output isn't correct
8 Incorrect 766 ms 61084 KB Output isn't correct