Submission #198419

#	Time	Username	Problem	Language	Result	Execution time	Memory
198419		model_code	Traffickers (RMI18_traffickers)	C++14	60 / 100	3612 ms	289056 KiB

traffickers

//  Author: Ștefan Constantin-Buliga
#include <fstream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <bitset>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <set>
#include <complex>

using namespace std;

const int SIZE = 1 << 10;

int pointer = SIZE;
char buffer[SIZE];

char Advance() {
    if (pointer == SIZE) {
        fread(buffer, 1, SIZE, stdin);
        pointer = 0;
    }
    return buffer[pointer++];
}

int Read() {
    int answer = 0;
    char ch = Advance();
    while (!isdigit(ch))
        ch = Advance();
    while (isdigit(ch)) {
        answer = answer * 10 + ch - '0';
        ch = Advance();
    }
    return answer;
}

const int MAXN = 30000;
const int MAXLOG = 14;
const int MAXD = 20;
const int MAXNODES = 131072;

vector<int> g[1 + MAXN];
int dad[1 + MAXLOG][1 + MAXN], depth[1 + MAXN], first[1 + MAXN], last[1 + MAXN], number = 0;

void DFS(int node, int father) {
    number++;
    first[node] = number;
    dad[0][node] = father;
    depth[node] = depth[father] + 1;
    for (int i = 1; (1 << i) < depth[node]; i++)
        dad[i][node] = dad[i - 1][dad[i - 1][node]];
    for (auto &son : g[node])
        if (son != father)
            DFS(son, node);
    number++;
    last[node] = number;
}

int Raise(int node, int delta) {
    if (delta < 0)
        return 0;
    for (int i = 0; i <= MAXLOG; i++)
        if (delta & (1 << i))
            node = dad[i][node];
    return node;
}

int Lca(int a, int b) {
    if (depth[a] < depth[b])
        swap(a, b);
    a = Raise(a, depth[a] - depth[b]);
    if (a == b)
        return a;
    for (int i = MAXLOG; i >= 0; i--)
        if (dad[i][a] != dad[i][b]) {
            a = dad[i][a];
            b = dad[i][b];
        }
    return dad[0][a];
}

struct Treap {
    int value;
    int priority;
    int add;
    int sum;
    Treap *left, *right;

    Treap() {
        value = 0;
        add = 0;
        sum = 0;
        priority = -1;
        left = right = NULL;
    }

    Treap(int _value, int _priority, int _add, Treap *_left, Treap *_right) {
        value = _value;
        priority = _priority;
        add = _add;
        left = _left;
        right = _right;
        Update();
    }

    void Update() {
        sum = left->sum + right->sum + add;
    }
};

Treap *nil, *tree[1 + MAXD][1 + MAXNODES];

pair<Treap*, Treap*> Split(Treap *node, int value) {
    if (node == nil)
        return make_pair(nil, nil);
    if (node->value <= value) {
        pair<Treap*, Treap*> temp = Split(node->right, value);
        node->right = temp.first;
        node->Update();
        return make_pair(node, temp.second);
    }
    else {
        pair<Treap*, Treap*> temp = Split(node->left, value);
        node->left = temp.second;
        node->Update();
        return make_pair(temp.first, node);
    }
}

Treap* Join(Treap *left, Treap *right) {
    if (left == nil)
        return right;
    if (right == nil)
        return left;
    if (left->priority > right->priority) {
        left->right = Join(left->right, right);
        left->Update();
        return left;
    }
    else {
        right->left = Join(left, right->left);
        right->Update();
        return right;
    }
}

void Initialize() {
    for (int i = 1; i <= MAXD; i++)
        for (int j = 1; j <= MAXNODES; j++)
            tree[i][j] = nil;
}

bool Find(Treap *node, int value) {
    if (node == nil)
        return false;
    if (node->value == value)
        return true;
    if (value < node->value)
        return Find(node->left, value);
    else
        return Find(node->right, value);
}

Treap* Insert(Treap *node, int value, int priority, int add) {
    if (priority < node->priority) {
        if (value < node->value)
            node->left = Insert(node->left, value, priority, add);
        else
            node->right = Insert(node->right, value, priority, add);
        node->Update();
        return node;
    }
    pair<Treap*, Treap*> temp = Split(node, value);
    return new Treap(value, priority, add, temp.first, temp.second);
}

Treap *Erase(Treap *node, int value, int add) {
    if (node->value == value) {
        node->add += add;
        node->Update();
        if (node->add == 0)
            node = Join(node->left, node->right);
        return node;
    }
    if (value < node->value)
        node->left = Erase(node->left, value, add);
    else
        node->right = Erase(node->right, value, add);
    node->Update();
    return node;
}

void Update(int id, int node, int left, int right, int where, int t, int add) {
    if (!Find(tree[id][node], t))
        tree[id][node] = Insert(tree[id][node], t, rand(), add);
    else
        tree[id][node] = Erase(tree[id][node], t, add);
    if (left == right)
        return;
    int middle = (left + right) / 2;
    if (where <= middle)
        Update(id, 2 * node, left, middle, where, t, add);
    else
        Update(id, 2 * node + 1, middle + 1, right, where, t, add);
}

void AddTraficker(int a, int b, int add) {
    int c = Lca(a, b), d = depth[a] - depth[c] + depth[b] - depth[c] + 1;
    for (int node = a, t = 0; node != c; node = dad[0][node], t++) {
        Update(d, 1, 1, number, first[node], t, add);
        Update(d, 1, 1, number, last[node], t, -add);
    }
    Update(d, 1, 1, number, first[c], depth[a] - depth[c], add);
    Update(d, 1, 1, number, last[c], depth[a] - depth[c], -add);
    for (int node = b, t = d - 1; node != c; node = dad[0][node], t--) {
        Update(d, 1, 1, number, first[node], t, add);
        Update(d, 1, 1, number, last[node], t, -add);
    }
}

int Query(int id, int node, int left, int right, int from, int to, int x, int y) {
    if (from <= left && right <= to) {
        pair<Treap*, Treap*> first = Split(tree[id][node], x - 1), second = Split(first.second, y);
        int answer = second.first->sum;
        tree[id][node] = Join(first.first, Join(second.first, second.second));
        return answer;
    }
    int answer = 0, middle = (left + right) / 2;
    if (from <= middle)
        answer += Query(id, 2 * node, left, middle, from,  to, x, y);
    if (middle + 1 <= to)
        answer += Query(id, 2 * node + 1, middle + 1, right, from, to, x, y);
    return answer;
}

int Get(int a, int b, int c, int d, int temp, int x, int y) {
    int answer = 0;
    answer += Query(d, 1, 1, number, first[c], first[a], x, y);
    if (temp)
        answer += Query(d, 1, 1, number, first[temp], first[b], x, y);
    return answer;
}

long long GetAnswer(int a, int b, int x, int y) {
    int c = Lca(a, b), temp = Raise(b, depth[b] - depth[c] - 1);
    long long answer = 0;
    for (int d = 1; d <= MAXD; d++) {
        if (y - x + 1 <= d && x % d <= y % d) {
            answer += Get(a, b, c, d, temp, x % d, y % d);
            continue;
        }
        int x0 = x - x % d + d - 1, y0 = y - y % d;
        answer += Get(a, b, c, d, temp, x % d, d - 1) + Get(a, b, c, d, temp, 0, y % d);
        if (x0 + 1 <= y0 - 1)
            answer += 1LL * ((y0 - x0 - 1) / d) * Get(a, b, c, d, temp, 0, d - 1);
    }
    return answer;
}

int main() {
    //freopen("tema.in", "r", stdin);
    //freopen("tema.out", "w", stdout);
    nil = new Treap();
    nil->left = nil->right = nil;
    int n = Read();
    for (int i = 1; i < n; i++) {
        int a = Read(), b = Read();
        g[a].push_back(b);
        g[b].push_back(a);
    }
    DFS(1, 0);
    Initialize();
    int k = Read();
    for (int i = 1; i <= k; i++) {
        int a = Read(), b = Read();
        AddTraficker(a, b, 1);
    }
    int q = Read();
    for (int i = 1; i <= q; i++) {
        int type = Read();
        if (type != 3) {
            int a = Read(), b = Read();
            if (type == 1)
                AddTraficker(a, b, 1);
            else
                AddTraficker(a, b, -1);
        }
        else {
            int a = Read(), b = Read(), x = Read(), y = Read();
            printf("%lld\n", GetAnswer(a, b, x, y));
        }
    }
    return 0;
}

Compilation message (stderr)

traffickers.cpp: In function 'char Advance()':
traffickers.cpp:26:14: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         fread(buffer, 1, SIZE, stdin);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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