Submission #850645

#	Time	Username	Problem	Language	Result	Execution time	Memory
850645		danikoynov	Tourism (JOI23_tourism)	C++14	28 / 100	5096 ms	31312 KiB

tourism

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10;

struct query
{
    int l, r, idx;
} task[maxn];

int n, m, c[maxn], q;
vector < int > adj[maxn];

void input()
{
    cin >> n >> m >> q;
    for (int i = 1; i < n; i ++)
    {
        int v, u;
        cin >> v >> u;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }

    for (int i = 1; i <= m; i ++)
    {
        cin >> c[i];
    }

    for (int i = 1; i <= q; i ++)
    {
        cin >> task[i].l >> task[i].r;
        task[i].idx = i;
    }
}


int depth[maxn], tin[maxn], tout[maxn];
int occ[2 * maxn], rev[2 * maxn], timer;

void euler(int v = 1, int p = - 1)
{
    occ[++ timer] = v;
    tin[v] = timer;
    rev[timer] = v;
    for (int u : adj[v])
    {
        if (u == p)
            continue;
        depth[u] = depth[v] + 1;
        euler(u, v);
        occ[++ timer] = v;
    }
    tout[v] = timer;
}

const int maxlog = 20;

int lg[2 * maxn], dp[maxlog][2 * maxn];

void sparse_table()
{
    for (int i = 1; i <= timer; i ++)
    {
        lg[i] = lg[i / 2] + 1;
        dp[0][i] = occ[i];
    }

    for (int j = 1; j < lg[timer]; j ++)
        for (int i = 1; i <= timer - (1 << j); i ++)
        {
            dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
            if (depth[dp[j - 1][i]] < depth[dp[j][i]])
                dp[j][i] = dp[j - 1][i];
        }
}

int get_lca(int v, int u)
{
    int l = tin[v], r = tin[u];
    if (l > r)
        swap(l, r);
    int len = lg[r - l + 1] - 1;
    int lca = dp[len][r - (1 << len) + 1];
    if (depth[dp[len][l]] < depth[lca])
        lca = dp[len][l];
    return lca;
}

int get_distance(int v, int u)
{
    return depth[v] + depth[u] - 2 * depth[get_lca(v, u)];
}

/**bool cmp_tin(int v, int u)
{
    return tin[v] < tin[u];
}
void solve_query(int lf, int rf)
{
    vector < int > ord;
    int global_lca = c[lf];
    for (int i = lf; i <= rf; i ++)
    {
        ord.push_back(c[i]);
        global_lca = get_lca(global_lca, c[i]);
    }

    sort(ord.begin(), ord.end(), cmp_tin);

    int ans = 0;
    for (int i = 0; i < ord.size(); i ++)
    {
        ans = ans + depth[ord[i]] - depth[global_lca];
        if (i > 0)
        {
            ans = ans - (depth[get_lca(ord[i - 1], ord[i])] - depth[global_lca]);
        }
    }
    cout << ans  + 1 << endl;
}*/

const int block_size = sqrt(maxn);
bool cmp_mo(query a, query b)
{
    if (a.l / block_size == b.l / block_size)
        return a.r < b.r;

    return a.l / block_size < b.l / block_size;
}


int lf = 1, rf, cost;
int fen[2 * maxn], act_cnt[maxn];

void update(int v, int val)
{
    //cout << "update " << val << endl;
    for (int i = v; i <= timer; i += (i & -i))
        fen[i] += val;
}

int query_sum(int v)
{
    int s = 0;
    for (int i = v; i > 0; i -= (i & -i))
        s += fen[i];
    return s;
}

int get_kth(int k)
{
    if (k == 0) /// corner case?
        return 0;
    ///cout << "get_kth " << k << endl;
    int sum = 0, pos = 0;
    for (int bit = maxlog - 1; bit >= 0; bit --)
    {
        if ((pos | (1 << bit)) > timer)
            continue;

        int new_pos = (pos | (1 << bit));
        ///cout << "transition " << pos << " " << new_pos << " " << sum + fen[new_pos] << " " << fen[new_pos] << endl;
        if (sum + fen[new_pos] < k)
        {
            sum = sum + fen[new_pos];
            pos = new_pos;
        }
    }

    return pos + 1;
}


set < int > act;
void add_vertex(int ver)
{
    act_cnt[ver] ++;
    if (act_cnt[ver] > 1)
        return;
    act.insert(tin[ver]);
    set < int > :: iterator it = act.find(tin[ver]);
    int bef = 0, aft = timer + 1;
    if (it != act.begin())
        bef = *prev(it);
    if (next(it) != act.end())
        aft = *next(it);
    ///int sm = query_sum(tin[ver]);
    ///int bef = get_kth(sm);
    ///int aft = get_kth(sm + 1);
    ///cout << "add " << rev[bef] << " " << ver << " " << rev[aft] << endl;
    if (bef != 0 && aft != timer + 1)
        cost = cost + depth[get_lca(rev[bef], rev[aft])];
    cost = cost + depth[ver];
    if (bef != 0)
        cost = cost - depth[get_lca(rev[bef], ver)];
    if (aft != timer + 1)
        cost = cost - depth[get_lca(ver, rev[aft])];

    ///update(tin[ver], 1);
}

void remove_vertex(int ver)
{
    act_cnt[ver] --;
    if (act_cnt[ver] > 0)
        return;
    ///update(tin[ver], -1);
    set < int > :: iterator it = act.find(tin[ver]);
    int bef = 0, aft = timer + 1;
    if (it != act.begin())
        bef = *prev(it);
    if (next(it) != act.end())
        aft = *next(it);
    act.erase(tin[ver]);
    /**int sm = query_sum(tin[ver]);
    int bef = get_kth(sm);
    int aft = get_kth(sm + 1);*/

    ///cout << "rem " << rev[bef] << " " << ver << " " << rev[aft] << endl;
    if (bef != 0 && aft != timer + 1)
        cost = cost - depth[get_lca(rev[bef], rev[aft])];

    cost = cost - depth[ver];
    if (bef != 0)
        cost = cost + depth[get_lca(rev[bef], ver)];
    if (aft != timer + 1)
        cost = cost + depth[get_lca(ver, rev[aft])];
}

void solve_query(int l, int r)
{
    while(rf < r)
    {
        rf ++;
        add_vertex(c[rf]);
    }


    while(lf > l)
    {
        lf --;
        add_vertex(c[lf]);
    }

    while(rf > r)
    {
        remove_vertex(c[rf]);
        rf --;
    }

    while(lf < l)
    {
        remove_vertex(c[lf]);
        lf ++;
    }
}

int tree[4 * maxn];

void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root] = c[left];
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root] = get_lca(tree[root * 2], tree[root * 2 + 1]);
}

int query_lca(int root, int left, int right, int qleft, int qright)
{
    if (left == qleft && right == qright)
        return tree[root];

    int mid = (left + right) / 2;
    if (qright <= mid)
        return query_lca(root * 2, left, mid, qleft, qright);
    if (qleft > mid)
        return query_lca(root * 2 + 1, mid + 1, right, qleft, qright);

    return get_lca(query_lca(root * 2, left, mid, qleft, mid),
                   query_lca(root * 2 + 1, mid + 1, right, mid + 1, qright));

}
int res[maxn];
void queries()
{
    build_tree(1, 1, m);
    sort(task + 1, task + q + 1, cmp_mo);
    for (int i = 1; i <= q; i ++)
    {
        solve_query(task[i].l, task[i].r);
        ///cout << "cost " << cost << endl;
        ///if (i == 2)exit(0);
        int global_lca = query_lca(1, 1, m, task[i].l, task[i].r);
        //for (int j = task[i].l; j <= task[i].r; j ++)
        //  global_lca = get_lca(global_lca, c[j]);

        res[task[i].idx] = cost - depth[global_lca] + 1;
    }
    for (int i = 1; i <= q; i ++)
        cout << res[i] << endl;
}
void solve()
{
    input();
    euler();
    sparse_table();
    queries();
}

int main()
{
    speed();
    solve();
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41